题目描述

给你一串数列 $a_i$，对于一个质数 $p$，定义函数 $f(p)$ 表示数列中能被 $p$ 整除的数的个数。

给出 $m$ 组询问 $l,r$，询问 $[l,r]$ 区间内所有素数 $p$ 的 $f(p)$ 之和。

输入格式

第一行一个整数 $n$，$1\le n\le 10^6$。

第二行 $n$ 个整数 $x_i$，$2\le x_i\le 10^7$。

第三行一个整数 $m$，$1\le m\le 50000$。

接下来 $m$ 行，每行两个整数 $l_i,r_i$，表示一个询问，$2\le l_i\le r_i\le 2\times 10^9$。

输出格式

输出共 $m$ 行，每行一个整数，表示对第 $i$ 个询问的回答。

6
5 5 7 10 14 15
3
2 11
3 12
4 4

9
7
0

7
2 3 5 7 11 4 8
2
8 10
2 123

0
7