3090 - 数论基础1-统计素数

有n个询问,你需要统计L到R范围内,有多少个数是素数。

输入

第一行一个整数n,表示询问个数。

接下来n行,每行两个整数L和R

输出

对于每个询问,输出一个整数,表示这个区间素数的个数。

样例

输入

3
1 5
4 10
7 13

输出

3
2
3

提示

50%的数据,满足$1≤L,R≤5∗10^3,n≤10^3$

70%的数据,满足$1≤L,R≤5∗10^5,n≤10^3$

100%的数据,满足$1≤L,R≤5∗10^6,n≤10^5$

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题