## MOG Round #15## Ended |

Almost prime numbers are the non-prime numbers which are divisible by only a single prime number. In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.

First line of the input file contains an integer
**
N (N <= 600)
**
which indicates how many sets of inputs are there. Each of the next N lines make a single set of input. Each set contains two integer numbers
**
low
**
and
**
high (0 < low <= high < 10
^{
12
}
)
**
.

For each line of input except the first line you should produce one line of output. This line contains a single integer, which indicates how many almost prime numbers are within the range (inclusive)
**
low…high
**
.

Input

3
1 10
1 20
1 5

Output

3
4
1