Số nguyên tố là số nguyên dương lớn hơn \(1\) và có đúng hai ước số dương là \(1\) và chính nó. Một số nguyên \(x\) được gọi là số nguyên tố đặc biệt nếu \(x\) là số nguyên tố và số viết ngược lại của \(x\) cũng là số nguyên tố.

Ví dụ: Số \(13\) là số nguyên tố đặc biệt vì \(13\) và \(31\) đều là số nguyên tố, số \(23\) không phải là số nguyên tố đặc biệt vì \(23\) là số nguyên tố nhưng \(32\) không phải là số nguyên tố.

Cho dãy số \(A\) có \(N\) phần tử nguyên \(A_1, A_2, \dots, A_N\) và một số nguyên dương \(Q\).

Yêu cầu: Với mỗi cặp chỉ số \(L, R\) (\(1 \le L \le R \le N\)) trong \(Q\) truy vấn, đếm số lượng số nguyên tố đặc biệt trong đoạn con \(A_L, A_{L+1}, \dots, A_R\).

Input

• Dòng 1: Ghi hai số nguyên dương \(N, Q\) (\(1 \le N \le 10^6; 1 \le Q \le 10^6\)).
• Dòng 2: Ghi \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^7 \le A_i \le 10^7; i = 1, 2, \dots, N\)).
• \(Q\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(L, R\) (\(1 \le L \le R \le N\)).

Output

• Ghi ra \(Q\) dòng, mỗi dòng ghi một số nguyên là kết quả tương ứng với mỗi truy vấn.

Example

5 3
13 23 31 7 11
1 3
2 4
1 5

2
2
4

Constraints

• Subtask \(1\) (\(30\%\) số điểm): \(N, Q \le 10^3; |A_i| \le 10^6\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.