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ố \(51\) là số đặc biệt vì \(5 + 1 = 6\) và \(51\) chia hết cho \(6\);
• Số \(20\) là số đặc biệt vì \(2 + 0 = 2\) và \(20\) chia hết cho \(2\);
• Số \(13\) không phải là số đặc biệt vì \(1 + 3 = 4\) và 13 không chia hết cho \(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, ..., 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, ..., A_R\) có bao nhiêu phần tử là số đặc biệt.

Dữ liệu vào

• 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, ..., A_N\) \((1 \le A_i \le 10^9)\);
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(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.

Dữ liệu ra

• \(Q\) dòng, mỗi dòng là số lượng số đặc biệt trong dãy con \(A_L, ..., A_R\) tương ứng.

Input 1

8 3
2 18 26 20 5 28 36 39
1 5
3 3
3 8

Output 1

4
0
3