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

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