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.

Bộ test gồm 50 testcase, có test biên, test subtask nhỏ và test sát giới hạn.

Subtask

• 40% s? ?i?m: ~Q=1~, ~L=1~, ~R=n~.
• 40% s? ?i?m: ~Q \le 10^3~.
• 20% s? ?i?m: ~1 \le n,Q \le 10^5~, ~1 \le a_i \le 10^9~.