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ố. nguyên tố.

+ Thêm vào bên phải của x một trong các số từ 0 tới 9, số thu được cũng là số

-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 số 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 ai, a2, ..., az 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.

Dữ liệu vào: Từ tệp văn bản SNTOTD.INP gồm:

+ Dòng đầu chứa số nguyên n (1 ≤ n ≤ 10^5).

+ Dòng thứ hai chứa n số nguyên dương ai, a2,..., a₂ (1 ≤ a ≤ 10^6; 1 ≤ i ≤ n).

+ Dòng thứ ba chứa số nguyên m là số lượng câu hỏi (1 ≤ m ≤ 105).

+ m dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v (1 ≤ u ≤ v≤ n).

Kết quả: 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.

Ví dụ:  

6
59 12 57 53 23 313
3
1 3
2 5
3 6

Ouput:

1

1

2

Giải thích:

-Có 1 số nguyên tố toàn diện là 59 trong đoạn từ 1 tới 3.
-Có 1 số nguyên tố toàn diện là 23 trong đoạn từ 2 tới 5.
- Có 2 số nguyên tố toàn diện là 23 và 313 trong đoạn từ 3 tới 6.

C++