Một số là đặc biệt nếu nó chia hết cho tổng các chữ số của chính nó.

Cho dãy ~a~ gồm ~n~ số và ~Q~ truy vấn đoạn ~[L,R]~. Với mỗi truy vấn, hãy đếm số phần tử đặc biệt trong đoạn đó.

Input

Dòng đầu chứa ~n, Q~ ~(1 \le n,Q \le 10^5)~.

Dòng thứ hai chứa ~n~ số ~a_i~ ~(1 \le a_i \le 10^9)~.

~Q~ dòng tiếp theo, mỗi dòng chứa ~L, R~.

Output

In ra đáp án của từng truy vấn.

Subtask

• 100% số điểm: không có ràng buộc bổ sung ngoài các giới hạn đã nêu ở phần Input.

Ví dụ 1

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

4
0
3

Ví dụ 2

16 1
8383 7372 9816 3008 1646 6445 3369 882 6856 8302 3480 4506 9741 8685 7828 4558
2 13

4