402362: GYM100738 H K-palindrome

Let's have K natural numbers: b₁, b₂, ..., b_k. We say that X (in base 10) is K-palindrome if there exist at least one b_i such as X written in base b_i is a palindrome.

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

First line of the input contains number K (1 ≤ K ≤ 13). The next line has K numbers, representing the array b (2 ≤ b_i ≤ 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).

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

2
2 3
2
0 10
11 15

10
2