Nguyên tố

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, \ldots, 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}, \ldots, A_R$.

Đọc từ tệp văn bản NGUYENTO.INP gồm:

• 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, \ldots, A_N$ ($-10^7 \le A_i \le 10^7$; $i = 1, 2, \ldots, 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 trong các tệp dữ liệu cách nhau bởi dấu cách.

Ghi ra tệp văn bản NGUYENTO.OUT 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 tệp dữ liệu vào.

• Subtask 1: Có 40% test với $Q = 1$; $1 \le N \le 10^3$;
• Subtask 2: Có 30% test với $Q = 1$; $1 \le N \le 10^6$; $1 \le A_i \le 10^6$; $i = 1, 2, \ldots, N$;
• Subtask 3: Có 30% 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.