Recently, the bear started studying data structures and faced the following problem.

You are given a sequence of integers $*x*_{1}, *x*_{2}, ..., *x*_{*n*}$ of length $*n*$ and $*m*$ queries, each of them is characterized by two integers $*l*_{*i*}, *r*_{*i*}$. Let's introduce $*f*(*p*)$ to represent the number of such indexes $*k*$, that $*x*_{*k*}$ is divisible by $*p*$. The answer to the query $*l*_{*i*}, *r*_{*i*}$ is the sum: , where $*S*(*l*_{*i*}, *r*_{*i*})$ is a set of prime numbers from segment $[*l*_{*i*}, *r*_{*i*}]$ (both borders are included in the segment).

Help the bear cope with the problem.

Input

The first line contains integer $*n*$ $(1 ≤ *n* ≤ 10^{6})$. The second line contains $*n*$ integers $*x*_{1}, *x*_{2}, ..., *x*_{*n*}$ $(2 ≤ *x*_{*i*} ≤ 10^{7})$. The numbers are not necessarily distinct.

The third line contains integer $*m*$ $(1 ≤ *m* ≤ 50000)$. Each of the following $*m*$ lines contains a pair of space-separated integers, $*l*_{*i*}$ and $*r*_{*i*}$ $(2 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ 2·10^{9})$ — the numbers that characterize the current query.

Output

Print $*m*$ integers — the answers to the queries on the order the queries appear in the input.

Note

Consider the first sample. Overall, the first sample has 3 queries.

1. The first query $*l* = 2$, $*r* = 11$ comes. You need to count $*f*(2) + *f*(3) + *f*(5) + *f*(7) + *f*(11) = 2 + 1 + 4 + 2 + 0 = 9$.
2. The second query comes $*l* = 3$, $*r* = 12$. You need to count $*f*(3) + *f*(5) + *f*(7) + *f*(11) = 1 + 4 + 2 + 0 = 7$.
3. The third query comes $*l* = 4$, $*r* = 4$. As this interval has no prime numbers, then the sum equals 0.