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 contains an integer which indicates how many sets of inputs are there. Each of the next lines is a separate test case that contains two integer numbers and .
For each test case print in a separate line the number of almost prime integers on a segment inclusive.