CF385C.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.

最近，小熊开始学习数据结构，并遇到了如下问题。

给定一个长度为 $n$ 的整数序列 $x_1, x_2, \dots, x_n$，以及 $m$ 个查询，每个查询由两个整数 $l_i, r_i$ 描述。定义函数 $f(p)$ 表示满足 $x_k$ 能被 $p$ 整除的下标 $k$ 的个数。查询 $l_i, r_i$ 的答案为如下求和式：
，
其中 $S(l_i, r_i)$ 是区间 $[l_i, r_i]$（含端点）内所有质数构成的集合。

请帮助小熊解决该问题。

The first line contains integer n (1 ≤ n ≤ 106). The second line contains n integers _x_1, _x_2, ..., x__n (2 ≤ x__i ≤ 107). 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·109) — the numbers that characterize the current query.

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）。第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$2 \leq x_i \leq 10^7$）。这些数不一定互不相同。

第三行包含一个整数 $m$（$1 \leq m \leq 50000$）。接下来的 $m$ 行中，每行包含一对用空格分隔的整数 $l_i$ 和 $r_i$（$2 \leq l_i \leq r_i \leq 2 \cdot 10^9$），表示当前查询的参数。

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

输出 m 个整数——即按输入中查询出现的顺序给出各查询的答案。

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.

考虑第一个样例。总体而言，第一个样例包含 3 个查询。

1. 第一个查询为 $l = 2$，$r = 11$。你需要计算 $f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9$。
2. 第二个查询为 $l = 3$，$r = 12$。你需要计算 $f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7$。
3. 第三个查询为 $l = 4$，$r = 4$。由于该区间内不含质数，因此和为 0。