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\mathbf{\ }\)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},\ldots,\ 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\).

Dữ liệu vào:

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

+ Dòng thứ hai ghi \(n\) số nguyên \(a_{1},\ a_{2},\ldots,a_{n}\ (1 \leq a_{i} \leq 10^{6}\); \(1 \leq i \leq n\)).

+ Dòng thứ ba chứa số nguyên \(m\) là số lượng câu hỏi \((1 \leq m \leq 10^{5})\).

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

Kết quả:

+ Ghi \(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ụ:

Ràng buộc:

+ 70% số test tương ứng với 70% số điểm có \(1 \leq n \leq 10^{3};1 \leq a_{i} \leq 10^{3}\);
\(1 \leq m \leq 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.