# 2790. prime expression

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 奖励。