Số \(x\) là số siêu nguyên tố tiềm năng khi thỏa mãn đồng thời \(3\) đ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ố trong khoảng \(0..9\), số thu được là số nguyên tố;
• Khi lần lượt xóa đi từng chữ số bên phải của \(x\), số thu được vẫn là số nguyên tố.

Yêu cầu: Cho dãy gồm \(N\) số nguyên dương \(a_1, a_2... a_n\) và \(T\) bộ số \(u, v\) \((1 \le u \le v \le n)\). Hãy đếm số lượng số siêu nguyên tố tiềm năng trong đoạn \(a_u...a_v\)

Input

• Dòng 1: Chứa số nguyên dương \(N\)
• Dòng 2: Chứa \(N\) số nguyên dương \(a_1, a_2... a_n\)
• Dòng 3: Chứa số nguyên dương \(T\) là số lượng câu hỏi
• \(T\) dòng tiếp theo, dòng thứ \(i\) chứa \(2\) số nguyên dương \(u, v\) \((1 \le u \le v \le n)\) ứng với câu hỏi thứ \(i\) là trong đoạn \(a_u...a_v\) có bao nhiêu số siêu nguyên tố tiềm năng.

Output

• Ghi ra trên \(T\) dòng, dòng thứ \(i\) là đáp án câu hỏi tương ứng.

Subtask 1

• \(1 \le T, N \le 10^{2}\)
• \(1 \le A_i \le 10^{3}\)

Subtask 2

• \(1 \le T, N \le 10^{3}\)
• \(1 \le A_i \le 10^{8}\)

Subtask 3

• \(1 \le T, N \le 10^{5}\)
• \(1 \le A_i \le 10^{6}\)

Sample Input 1

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

Sample Output 1

1
1
2