###### Category

###### Similar Problems

## 0758. Almost Prime Numbers

###### Time limit : 2000 ms

Memory limit : 64 mb

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** (1≤**n** ≤ **300**) 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**].

Samples

№ |
Input |
Output |

1 |
3 1 10 1 20 1 5 |
3 4 1 |

Text from: e-olimp.com