Competitions

# Azerbaijan Programming Olympiad - 2nd Stage preparation

# Almost Prime Numbers

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**].

Input example #1

3 1 10 1 20 1 5

Output example #1

3 4 1