#257. 玉户帘中卷不去

玉户帘中卷不去

题目描述

给定一个范围 nn, 对于 qq 个区间 [l,r][l, r], 求区间 [l,r][l, r] 内的素数个数

输入格式

第一行包含两个正整数 nn , qq ,分别表示查询的范围和查询的个数。

接下来 qq 行,每行包含 22 个不小于 11 且不大于 nn 的整数 ll, rr,即询问该区间内的素数个数。

输出格式

qq行, 输出每个区间内素数个数

样例

Input

10 2
2 5
3 6

Output

3
2

数据范围与提示

对于 10%10\% 的数据 ,1n,q101 \le n, q \le 10
对于 20%20\% 的数据, 1n,q100,0001 \le n, q \le 100,000
对于 30%30\% 的数据, 1n1000,000,1q10001 \le n \le 1000,000, 1 \le q \le 1000
对于 20%20\% 的数据, 1n,q1,000,0001 \le n, q \le 1,000,000
对于 20%20\% 的数据, 1n,q2,000,0001 \le n, q \le 2,000,000
请使用较快的 I/OI/O 方式