Problems
Almost Prime Numbers
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 data
First line contains an integer n~(n \le 600) which indicates how many sets of inputs are there. Each of the next n lines is a separate test case that contains two integer numbers low and high~(0 < low \le high \le 10^{12}).
Output data
For each test case print in a separate line the number of almost prime integers on a segment [low ... high] inclusive.
Examples
Input example #1
3 1 10 1 20 1 5
Output example #1
3 4 1