最近,小熊开始学习数据结构,面临以下问题。
给定一个长度为 n 和 m 个查询的整数 x1、x2、...、xn 序列,每个查询都由两个整数 li、ri 来表征。我们引入 f(p) 来表示此类索引 k 的数量,即 xk 可以被 p 整除。查询 li, ri 的答案是总和:$$\sum_{p \in S(l_i, r_i)} f(p)$$,其中 S(li, ri) 是段 [li, ri] 中的一组素数(两个边界都包含在该段中)。
帮助熊解决问题。
输入
第一行包含整数 n (1 ≤ n ≤ 106)。第二行包含 n 个整数 x1, x2, ..., xn (2 ≤ xi ≤ 107)。这些数字不一定是不同的。
第三行包含整数 m (1 ≤ m ≤ 50000)。以下 m 行中的每一行都包含一对空格分隔的整数 li 和 ri (2 ≤ li ≤ ri ≤ 2·109) — 表征当前查询的数字。
输出
打印 m 个整数 — 按照查询在输入中出现的顺序查询查询的答案。
示例
输入 #1
6 5 5 7 10 14 15 3 2 11 3 12 4 4
输出 #1
9 7 0
输入 #2
7 2 3 5 7 11 4 8 2 8 10 2 123
输出 #2
0 7
注意
考虑第一个样本。总的来说,第一个样本有 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。