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ố ~\in \{0,1,...,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ố.

Ví dụ : Số ~x=313~ là số siêu nguyên tố tiềm năng vì:

• ~x~ 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 ~31;3~ là các số nguyên tố.

Cho dãy gồm ~N~ số nguyên dương ~a_1,a_2,\ldots,a_n~ và ~T~ bộ (~u,v~) (~1\le u < 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_{u+1},\ldots,a_v~.

Input

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

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,\ldots,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 < v \le n~) ứng với câu hỏi thứ ~i~ là trong đoạn ~a_u,a_{u+1},\ldots,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 ~i~ trong file dữ liệu vào.

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ác số siêu nguyên tố tiềm năng trong dãy ban đầu là: ~59~,~23~,~313~.

Với câu hỏi 1, đoạn ~a_1,a_2,a_3~ có 1 số siêu nguyên tố tiềm năng là ~a_1=59~.