Một số nguyên dương ~x~ được gọi là số nguyên tố đẹp 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 số ~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 số ~x~ một chữ số bất kì thì số thu được cũng là số nguyên tố.

Ví dụ số ~313~ là số nguyên tố đẹp, vì:

• Số ~313~ là số nguyên tố;

• Bỏ chữ số ~3~ được số ~31~ là số nguyên tố, bỏ tiếp chữ số ~1~ ta còn số ~3~ cũng là số nguyên tố;

• Thêm số ~7~ vào sau số ~313~ ta được số ~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_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^6, 1 \le i \le n)~ và ~m~ truy vấn. Mỗi truy vấn có dạng ~(u, v)~ với ý nghĩa: đếm số lượng số nguyên tố đẹp trong dãy ~a~ từ vị trí ~u~ tới ~v~.

Input

• Dòng thứ nhất 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_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^6, 1 \le i \le n)~;

• Dòng thứ ba chứa số nguyên dương ~m~ là số lượng truy vấn ~(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

Gồm ~m~ dòng, mỗi dòng theo thứ tự của truy vấn ghi ra số lượng số nguyên tố đẹp tìm được.

Scoring

Sample Input 1

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

Sample Output 1

1
1
2

Notes

• Có ~1~ số nguyên tố đẹp là ~59~ trong đoạn từ ~1~ đến ~3~.

• Có ~1~ số nguyên tố đẹp là ~23~ trong đoạn từ ~2~ đến ~5~.

• Có ~2~ số nguyên tố đẹp là ~23~ và ~313~ trong đoạn từ ~3~ đến ~6~.