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\) (vì \(1+8=9\)).

Cho dãy \(A\) có \(n\) số nguyên dương \(\{a_1, a_2, \ldots, 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 \le l \le r \le 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.

Input

• Dòng đầu gồm hai số nguyên dương \(n, q\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\).
• \(q\) dòng tiếp theo, mỗi dòng gồm 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.

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le q \le 10^5\)
• \(1 \le a_i \le 10^9\) với mọi \(i = \overline{1, n}\)

Output

• Ghi ra \(q\) dòng, mỗi dòng là số lượng số đặc biệt trong đoạn \([l, r]\) tương ứng.

Example

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

4
0
3

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10^5, q = 1, l = 1, r = n\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 10^5, q \le 10^3\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.