Số nguyên tố là số có đúng hai ước nguyên dương là 1 và chính nó.

Một số nguyên dương x gọi là số nguyên tố toàn diện nếu đồng thời thỏa mãn cả 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 x một chữ số nào đó thì số thu được cũng là số nguyên tố.

Ví dụ: Số 313 là số nguyên tố toàn diện vì:</p>

- 313 là số nguyên tố

- Bỏ chữ số 3 bên phải: còn 31 → nguyên tố, tiếp tục bỏ 1 còn 3 → nguyên tố

- Thêm 7 bên phải: 3137 → nguyên tố

Yêu cầu:

Cho một dãy gồm n số nguyên dương a₁, a₂, ..., a_n và m câu hỏi. Mỗi câu hỏi là cặp số (u, v), yêu cầu đếm số lượng số nguyên tố toàn diện nằm trong đoạn chỉ số từ u đến v.

Dữ liệu vào:

Từ tệp văn bản SNTOTD.INP gồm:</p>

- Dòng 1: Số nguyên n (1 ≤ n ≤ 10⁵)

- Dòng 2: n số nguyên dương a₁, ..., a_n (1 ≤ a_i ≤ 10⁶)

- Dòng 3: Số nguyên m là số lượng câu hỏi (1 ≤ m ≤ 10⁵)

- m dòng tiếp theo: mỗi dòng chứa hai số nguyên u, v (1 ≤ u ≤ v ≤ n)

Dữ liệu ra:

Ghi ra file SNTOTD.OUT gồm m dòng, mỗi dòng là đáp án (số lượng số nguyên tố toàn diện) cho từng truy vấn trong file đầu vào.

Ví dụ:

SNTOTD.INP</p>

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

SNTOTD.OUT

1
1
2

Giải thích:

- Có 1 số nguyên tố toàn diện là 59 trong đoạn 1-3

- Có 1 số nguyên tố toàn diện là 23 trong đoạn 2-5

- Có 2 số nguyên tố toàn diện là 23 và 313 trong đoạn 3-6

Ràng buộc:

- 70% test ứng với n, a_i, m ≤ 10³</p>

- 30% test còn lại không giới hạn n, a_i, m