Số đặc biệt

Số đặc biệt là số có giá trị chia hết cho tổng các 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$ (vì $1+8=9$).

Cho dãy $A$ có $n$ số nguyên dương $\{a_1, a_2, \ldots, a_n\}$.

Yêu cầu: Có $q$ câu hỏi, mỗi câu hỏi cho biết hai số $l, r$ $(1 \le l \le r \le n)$; hãy cho biết trong mỗi đoạn $[l, r]$ của dãy $A$ có bao nhiêu phần tử là số đặc biệt.

• Dòng đầu gồm hai số nguyên dương $n, q$.
• Dòng thứ hai gồm $n$ số nguyên dương $a_1, a_2, \ldots, a_n$.
• $q$ dòng tiếp theo, mỗi dòng gồm hai số $l$ và $r$.
• Các số nguyên trong tệp dữ liệu được ghi cách nhau ít nhất một dấu cách trống.

• Ghi ra $q$ dòng, mỗi dòng là số lượng số đặc biệt trong đoạn $[l, r]$ tương ứng.

• $1 \le n \le 10^5$
• $1 \le q \le 10^5$
• $1 \le a_i \le 10^9$ với mọi $i = \overline{1, n}$

Chấm điểm:

• Subtask $1$ ($30\%$ số điểm): $n \le 10^5, q = 1, l = 1, r = n$.
• Subtask $2$ ($40\%$ số điểm): $n \le 10^5, q \le 10^3$.
• Subtask $3$ ($30\%$ số điểm): không có ràng buộc gì thêm.