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

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

Example

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

1
1
2

Scoring

• Có \(70\%\) số điểm thỏa mãn: \(1 \le a_i \le 10^3, 1 \le n \le 10^3, 1 \le m \le 10^3\).
• Có \(30\%\) số điểm còn lại: Không có ràng buộc gì thêm.