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. \InputFile 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})$. \OutputFile For each test case print in a separate line the number of almost prime integers on a segment $[low ... high]$ inclusive.