Số đặc biệt là số nguyên có giá trị chia hết cho tổng các chữ số của nó. Ví dụ: số 3 là số đặc biệt vì 3 chia hết cho 3, số 12 là số đặc biệt vì 12 chia hết cho 3 (~1 + 2 = 3~), số 15 không phải số đặc biệt vì 15 không chia hết cho 6 (~1 + 5 = 6~).

Yêu cầu: Cho dãy ~a~ gồm ~n~ số nguyên dương và ~Q~ dãy con của ~a~, mỗi dãy con được giới hạn bởi hai chỉ số ~L~ và ~R~. Hãy cho biết trong mỗi dãy con có bao nhiêu số là số đặc biệt.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~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, ..., a_n~ (~1 \le a_i \le 10^9~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số ~L~ và ~R~ (~1 \le L \le R \le n~).

Output

Ghi ra ~Q~ dòng, mỗi dòng là số lượng số đặc biệt trong dãy con tương ứng.

Sample Input 1

8 3
2 18 25 20 5 23 39 76
1 5
3 3
2 7

Sample Output 1

4
0
3

Giải thích:

• Dãy con ~a_1, ..., a_5~ có 4 số đặc biệt là 2, 18, 20, 5.
• Dãy con ~a_3~ là 25 không phải là số đặc biệt.
• Dãy con ~a_2, ..., a_7~ có 3 số đặc biệt là 18, 20, 5.

Ràng buộc

• 40% số test thoả mãn điều kiện: ~Q = 1, L = 1, R = n~.
• 40% số test thoả mãn điều kiện: ~Q \le 10^3~.
• 20% số test còn lại không có ràng buộc gì thêm.