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}, ..., 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}, ..., A_{R}~.

Input

• Dòng 1: Ghi 2 số nguyên dương ~N, Q~ trong đó ~N~ là số phần tử của dãy số ~A~ và ~Q~ là số truy vấn (~1 \le N \le 10^{6}~; ~1 \le Q \le 10^{6}~);
• Dòng 2: Ghi ~N~ số nguyên ~A_{1}, A_{2}, ..., A_{N}~ (~-10^{7} \le A_{i} \le 10^{7}~; ~i=1, 2, .., 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~).

Lưu ý: Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Gồm ~Q~ dòng, mỗi dòng ghi kết quả tìm được tương ứng với một cặp chỉ số ~L, R~ trong dữ liệu vào.

Sample Input 1

8 3
8 3 25 7 -5 13 2 -20
1 3
2 6
6 8

Sample Output 1

1
3
2

Subtasks

• Subtask 1: Có 40% số test với ~Q=1~; ~1 \le N \le 10^{3}~;
• Subtask 2: Có 30% số test với ~Q=1~; ~1 \le N \le 10^{6}~; ~1 \le A_{i} \le 10^{6}~; ~i=1, 2, .., N~;
• Subtask 3: Có 30% số test với ~Q \le 10^{6}~; ~1 \le N \le 10^{6}~; ~A_{i}~ không có ràng buộc gì thêm.