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 được 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 đến 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ố.
• 31 là số nguyên tố, 3 là số nguyên tố.
• Thêm số 7 vào sau 313 thì 3137 cũng là số nguyên tố.

Yêu cầu: Cho dãy A gồm n số nguyên dương a₁, a₂, …, aₙ 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ị trí v.

Input

• Dòng đầu tiên chứa số nguyên dương n ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ ~(1 \le a_i \le 10^6)~.
• Dòng thứ ba chứa số nguyên dương 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à 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ự.

Ràng buộc

• 70% số test có n, m nhỏ.
• 30% số test không có ràng buộc gì thêm.

Ví dụ

Sample Input

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

Sample Output

1
1
2