Số nguyên tố toàn diện

Hôm nay, An được học về số nguyên tố. Số nguyên tố là số có đúng hai ước nguyên dương là 1 và chính nó. Ví dụ số 17 là số nguyên tố nhưng số 16 thì không.

Vốn là người có nhiều ý tưởng sáng tạo, An đưa ra một khái niệm mới gọi là "số nguyên tố toàn diện". Một số nguyên dương $x$ gọi là số nguyên tố toàn diện nếu thỏa mãn đồng thời 3 điều kiện sau:

• $x$ là số nguyên tố.
• Lần lượt bỏ đi các chữ số bên phải của $x$ thì phần còn lại của nó vẫn là số nguyên tố.
• Thêm vào bên phải của $x$ một trong các chữ số từ 0 tới 9, số thu được cũng là số nguyên tố.

Ví dụ số 313 là số nguyên tố toàn diện vì:

• 313 là số nguyên tố.
• Bỏ đi số 3 bên phải ta còn số 31 là số nguyên tố, bỏ tiếp số 1 ta còn số 3 cũng là số nguyên tố.
• Thêm số 7 vào sau 313 ta được số 3137 là số nguyên tố.

Yêu cầu: Cho dãy $A$ gồm $n$ số nguyên dương $a_1, a_2, \dots, a_n$ và $m$ câu hỏi. Mỗi câu hỏi có dạng $(u, v)$ với ý nghĩa: Đếm số lượng số nguyên tố toàn diện trong dãy $A$ từ vị trí $u$ tới $v$.

Từ tệp văn bản SNTOTD.INP gồm:

• Dòng đầu chứa số nguyên $n$ ($1 \le n \le 10^5$).
• Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$; $1 \le i \le n$).
• Dòng thứ ba chứa số nguyên $m$ là số lượng câu hỏi ($1 \le m \le 10^5$).
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $u, v$ ($1 \le u \le v \le n$).

Ghi ra tệp văn bản SNTOTD.OUT $m$ dòng, mỗi dòng là đáp án của một câu hỏi theo thứ tự của các câu hỏi được đưa ra trong tệp dữ liệu vào.

• 70% số test tương ứng với 70% số điểm có $1 \le n \le 10^3$; $1 \le a_i \le 10^3$; $1 \le m \le 10^3$.
• 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.