2790. prime expression

单点时限: 2.0 sec

内存限制: 256 MB

There are some prime values, p, for which there exists a positive integer, n, such that the expression n3 + n2p is a perfect cube.

For example, when p = 19, 83 + 82 19 = 123.

What is perhaps most surprising is that for each prime with this property the value of n is unique, and there are only four such primes below one-hundred.

You’re given two numbers A and B ( 0<=A<=B<=1000000), find out How many primes between A and B have this remarkable property?

输入格式

The first line will be a number N(<=100), means that there’re N test cases , Then N lines follow,each with two numbers A and B as described above.

输出格式

Output one line,with the answer described above;

样例

Input
2
1 10
1 100
Output
1
4

15 人解决,25 人已尝试。

25 份提交通过,共有 67 份提交。

5.5 EMB 奖励。

创建: 10 年,9 月前.

修改: 3 年前.

最后提交: 2 年,5 月前.

来源: ECNU 2009 ACM selective trial From Project Euler

题目标签