Số đặc biệt

Trong một buổi học lập trình, thầy giáo đưa ra một bài toán thú vị về các con số đặc biệt. Biết rằng số đặc biệt là số có giá trị chia hết cho tổng các chữ số của nó. Chẳng hạn: số 5 là số đặc biệt vì 5 chia hết cho 5, số 20 là số đặc biệt vì 20 chia hết cho 2 $(2 + 0 = 2)$, số 13 không phải là số đặc biệt vì 13 không chia hết cho 4 $(1 + 3 = 4)$.

Thầy muốn kiểm tra khả năng lập trình của học sinh bằng cách cho trước một dãy số nguyên dương, học sinh cần xác định có bao nhiêu số đặc biệt trong một dãy con liên tiếp của dãy số đã cho.

Yêu cầu: Cho dãy $A$ có $N$ số nguyên dương $A_1, A_2, \dots, A_N$. Có $Q$ dãy con, mỗi dãy con được giới hạn bởi hai số nguyên dương $L$, $R$. Hãy cho biết trong mỗi dãy con $A_L, \dots, A_R$ có bao nhiêu phần tử là số đặc biệt.

Đọc từ tệp văn bản SODB.INP có cấu trúc:

• Dòng đầu chứa hai số nguyên dương $N, Q$ ($1 \le N \le 10^5$; $1 \le Q \le 10^5$);
• Dòng thứ hai chứa dãy $A$ gồm $N$ số nguyên dương $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$, $i = 1..N$).
• $Q$ dòng tiếp theo, mỗi dòng chứa hai số $L$ và $R$ ($1 \le L \le R \le N$).
• Các số nguyên trên một dòng được ghi cách nhau một khoảng trắng.

Ghi ra tệp văn bản SODB.OUT gồm $Q$ dòng, mỗi dòng là số lượng số đặc biệt trong dãy con $A_L, \dots, A_R$ tương ứng.

• Có 30% số điểm thỏa mãn điều kiện: $Q = 1, L = 1, R = N$;
• Có 40% số điểm thỏa mãn điều kiện: $Q \le 10^3$;
• Có 30% số điểm còn lại không có ràng buộc gì thêm.