Bài 2. 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 (1+8=9). Cho dãy A có n số nguyên dương {a_1,a_2,…,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≤l≤r≤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ữ liệu: Vào từ tệp văn bản BAI2.INP
Dòng một là hai số nguyên dương n,q (1≤n≤10^5,1≤q≤10^5);
Dòng hai là 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 có 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.
Kết quả: Ghi ra tệp văn bản BAI2.OUT q dòng, mỗi dòng là số lượng số đặc biệt trong đoạn [l,r] tương ứng.
Ví dụ:
BAI2.INP
8 3
2 18 26 20 5 28 36 39
1 5
3 3
3 8
BAI2.OUT
4
0
3

Giải thích

• Câu hỏi 1 đoạn [1, 5] có 4 số đặc biệt là 2, 18, 20 và 5, vì:
  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 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ì.