H. K-palindrome
time limit per test
0.5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Let's have K natural numbers: b1, b2, ..., bk. We say that X (in base 10) is K-palindrome if there exist at least one bi such as X written in base bi is a palindrome.

Answer Q queries of form: how many numbers from a range [L, U] are K-palindromes?

Input

First line of the input contains number K (1 ≤ K ≤ 13). The next line has K numbers, representing the array b (2 ≤ bi ≤ 100000). The third line contains number Q (1 ≤ Q ≤ 100000). Next Q lines contain two numbers L and U, describing queries, (0 ≤ L ≤ U ≤ 100000000).

Output

Answer each of the Q queries, one query per line.

Examples
Input
2
2 3
2
0 10
11 15
Output
10
2