F - Almost Prime

Time limit: 1 s
Memory limit: 128 MiB
Languages: C, C++, Java, JavaScript, ... (details)

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.

Input

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 ) .

Output

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 .

Sample test(s)

Input
3 1 10 1 20 1 5
Output
3 4 1