Đếm Số Cực Tốt

Một số nguyên dương $x$ được gọi là số cực tốt khi thỏa mãn đồng thời ba điều kiện sau:

• $x$ là số nguyên tố.
• Thêm vào bên phải số $x$ một chữ số $d \in {0, 1, ..., 9}$, số thu được $10x + d$ là số nguyên tố.
• Khi lần lượt xóa đi từng chữ số bên phải của $x$, tất cả các số thu được đều là số nguyên tố.

Ví dụ: Số $x = 313$ là một số cực tốt vì:

• $x = 313$ là số nguyên tố.
• Thêm vào bên phải số $x$ chữ số $7$, ta thu được $3137$ cũng là số nguyên tố.
• Khi lần lượt xóa đi các chữ số bên phải của $x$, ta thu được các số $31$ và $3$ đều là số nguyên tố.

Cho dãy gồm $N$ số nguyên dương $a_1, a_2, ..., a_N$ và $T$ truy vấn, mỗi truy vấn gồm một cặp số $(u, v)$ ($1 ≤ u < v ≤ N$). Hãy đếm số lượng số cực tốt trong đoạn $a_u, a_{u+1}, ..., a_v$.

Dữ liệu vào

Dữ liệu vào gồm:

• Dòng thứ nhất chứa số nguyên dương $N$ ($1 ≤ N ≤ 10^5$).
• Dòng thứ hai chứa $N$ số nguyên dương $a_1, a_2, ..., a_N$ ($1 ≤ a_i ≤ 10^8$).
• Dòng thứ ba chứa số nguyên dương $T$ ($1 ≤ T ≤ 10^5$) là số lượng câu hỏi.
• $T$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $u$ và $v$ ($1 ≤ u < v ≤ N$) ứng với câu hỏi thứ $i$.

Kết quả

In ra $T$ dòng, dòng thứ $i$ chứa số nguyên là đáp án cho câu hỏi thứ $i$.

Chấm điểm

Subtask 1 (25 points). $T = 1$; $N ≤ 100$

Subtask 2 (35 points). $T ≤ 10$; $N ≤ 10^3$

Subtask 3 (40 points). $1 ≤ N ≤ 10^5$; $1 ≤ T ≤ 10^5$

Ví dụ

Input

5
2 4 37 10 23
2
1 3
2 4

Output

2
1

Ghi chú

Trong ví dụ trên, các số cực tốt trong dãy ban đầu là $a_1 = 2$, $a_3 = 37$ và $a_5 = 23$.

• Với câu hỏi 1, đoạn $a_1, a_2, a_3$ có 2 số cực tốt là $a_1 = 2$ và $a_3 = 37$.
• Với câu hỏi 2, đoạn $a_2, a_3, a_4$ có 1 số cực tốt là $a_3 = 37$.

Các giới hạn phụ:

• Subtask 1 ($25%$ điểm): $T = 1$, $N ≤ 100$, $a_i ≤ 10^3$.
• Subtask 2 ($35%$ điểm): $T ≤ 10$, $101 ≤ N ≤ 10^3$, $a_i ≤ 10^8$.
• Subtask 3 ($40%$ điểm): $T ≤ 10^5$, $10^3 + 1 ≤ N ≤ 10^5$, $a_i ≤ 10^6$.