Số đặc biệt là số có giá trị chia hết cho tổng chữ số của nó. Ví dụ số ~ 2 ~ và ~ 18 ~ là số đặc biệt vì: ~ 2 ~ chia hết cho ~ 2 ~; ~ 18 ~ chia hết cho ~ 9 (1+8=9) ~. Cho dãy ~ A ~ có ~ n ~ số nguyên dương ~ a_1,a_2,…,a_n~ . Có ~ q ~ câu hỏi, mỗi câu hỏi cho biết ~ 2 ~ số ~ l,r 1≤l≤r≤n. ~

Yêu cầu: Hãy cho biết với mỗi câu hỏi, trong đoạn ~ l,r ~ của dãy ~ A ~ có bao nhiêu phần tử là số đặc biệt?

Dữ liệu vào:

• Dòng một chứa hai số nguyên dương ~ n,q (1≤n≤10^5, 1≤q≤10^5) ~;
• Dòng thứ hai dãy ~ A ~ chứa~ n ~ số nguyên dương ~ a_1,a_2,…,a_n (1≤a_i≤10^9, ∀i=1;n) ~.
• ~ q ~ dòng tiếp theo, mỗi dòng chứa hai số ~ l ~ và ~ r ~.

Kết quả: + Ghi ~ q ~ dòng, mỗi dòng là số lượng số đặc biệt trong đoạn ~ l,r ~.

Ví dụ:

Input

8 3
2 18 26 20 5 28 36 39
1 5
3 3
3 8 

Output

4
0
3 

Giải thích:

• Câu hỏi 1 trong đoạn [1, 5] có:
  • 2 chia hết cho 2;
  • 18 chia hết cho 9 (1+8=9);
  • 20 chia hết cho 2 (2+0=2);
  • 5 chia hết cho 5.
• Câu hỏi 2 đoạn [3, 3]: không có số đặc biệt.
• Câu hỏi 3 đoạn [3, 8]: có ba số đặc biệt là: 20, 5 và 36.

Ràng buộc:

• 30% số test tương ứng với 30% số điểm có ~ n≤10^5, q=1, l=1, r=n ~;
• 40% số test tương ứng với 40% số điểm có ~ n≤10^5, q≤10^3 ~;
• 30% số test tương ứng với 30% số điểm không có ràng buộc gì.