(sodbhp.*)

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},\ldots,a_{n}\}\) . Có \(q\) câu hỏi, mỗi câu hỏi cho biết \(2\) số \(l,r\ (1 \leq l \leq r \leq n).\)

Yêu cầu: Hãy cho biết với mỗi câu hỏi, trong đoạn \(\lbrack l,r\rbrack\) 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 \leq n \leq 10^{5},\ 1 \leq q \leq 10^{5})\);

• Dòng thứ hai dãy \(A\) chứa\(\ n\) số nguyên dương \(a_{1},a_{2},\ldots,a_{n}\ (1 \leq a_{i} \leq 10^{9},\ \ \forall i = \overline{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 \(\lbrack l,r\rbrack\).

Ví dụ:

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 (1+8=9);

20 chia hết cho (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 3\(0\%\) số điểm có \(n \leq 10^{5},\ q = 1,\ l = 1,\ r = n\);

• \(40\%\) số test tương ứng với 4\(0\%\) số điểm có \(n \leq 10^{5},\ q \leq 10^{3}\);

• \(30\%\) số test tương ứng với \(30\%\) số điểm không có ràng buộc gì.