A9313 | Bear and Prime Numbers

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.

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.

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