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, \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\).

Input

Vào từ file SNTOTD.INP:

• 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, \ldots, 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)\).

Output

Ghi ra file 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.

Example

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

1
1
2

Scoring

• \(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.