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 n (n≤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≤high≤1012).
For each test case print in a separate line the number of almost prime integers on a segment [low...high] inclusive.