Problem A: 统计质数

Memory Limit：512 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：24 Solved：2

Description

“2，3，5，7……1311，1917……”
“冷静，我得心平气和地思考才行，此时我该如何是好呢？”
“我得冷静下来……数质数向来都能让我冷静下来……”
“质数是只有 1 及自己能够整除的孤独数字……这些数字一直带给我莫

大的勇气……”

David Tao 是一个高中生，闲来无事时他在纸上写下了 n 个正整数，并定义函数
cnt(p) 表示这 n 个数中能被质数 p 整除的数的个数。而对于一个不是质数的数 a，定义
cnt(a) 的值为 0。
现在 David 想询问：这个函数在某一段区间上的取值之和，即对于一组给定的 L R，
∑R i=L cnt(i) 等于多少。询问共有 m 组。




Input

第一行包含两个正整数 n 和 m，分别表示写下的数的数量，以及询问组数。
第二行包含 n 个正整数，表示 n 个数的值。
接下来 m 行，每行包含两个正整数 L 和 R，表示提出询问的区间。

Output

输出共 m 行，每行包含一个正整数，表示每组询问的答案，由于答案可能很大，只
需要输出其对 109 + 7 取模后的结果即可。

Sample Input Copy 

5 3
4 6 7 9 11
2 3
1 4
1 5

Sample Output Copy 

4
4
4

HINT

David 一共写下了 5 个数：4, 6, 7, 9, 11，并进行了 3 次询问：
- [2, 3] 区间中有两个质数 2 和 3，其中 2 能够整除 4 和 6，故 cnt(2) = 2，而 3 能够
整除 6 和 9，故 cnt(3) = 2，所以 ∑3i=2 cnt(i) = 4。
- [1, 4] 区间中也只有两个质数 2 和 3，故这一问答案和上一问相同，即 ∑4i=1 cnt(i) = 4。
- [1, 5] 区间中有三个质数 2, 3 和 5，但是 5 不能整除任何一个数，故 cnt(5) = 0，故

这一问答案和前两问相同，即 ∑5 i=1 cnt(i) = 4。



对于 100% 的数据，保证 David 写下的数不大于 107，且 1 ⩽ L ⩽ R ⩽ 107。
测试点数量   n ⩽   m ⩽
      20%        10    106
      10%     1000     10
      20%     1000   106
      15%       106    10
      25%       106  106
此外共有 35% 的数据，保证 R − L ⩽ 50。