问题 F: 区间质数个数

问题 F: 区间质数个数

时间限制: 1 Sec  内存限制: 256 MB
提交: 447  解决: 95
[提交][状态][讨论版][命题人:]

题目描述

  为了研究素数的分布规律，需要提供n份样本数据，每份样本数据都有一个整数区间，现在要请你帮忙求出每份样本数据，这个整数区间都有多少个素数。

输入

一个整数n

接下来是n行，每行有两个整数ai,bi,数据保证ai<bi。


输出

一共n行，每行一个整数表示一个整数区间内的素数个数

样例输入

5
10 100
100 1000
1000 10000
10000 100000
100000 1000000

样例输出

21
143
1061
8363
68906

提示


50%的数据







1<=n<=10^4



1<=ai,bi<10^5


100%的数据






1<=n<=10^6



1<=ai,bi<10^7

[提交][状态]