Zoro while studying numbers, observed an interesting property. He found out that every number can be represented as powers of primes. Now getting bored from studying, he thought of having some fun and defined an Inversion Number.

An Inversion Number of a number is defined as interchanging the power of the prime with the prime number in the prime factorization of the number.

Eg: $24= 2^{3}$ x $3^{1}$

Inversion Number of $(24)= 3^{2}$ x $1^{3}$ 9

Zoro likes a number who's inversion number is unity. He calls them Perfect Inversion Numbers.
Now Zoro wonders given a range L to R what are the number of perfect inversion numbers in that range.

Note

Inversion number of 0 is 0 and inversion number of 1 is 1.

Input

First line contains an integer T denoting the number of testcases. Next T lines contains 2 integers each the range L and R.

Output

The number of Perfect Inversion Number between the the range L and R (both inclusive).

Constraints:

$1\leq T \leq 10^{6}$
$0\leq L\leq R\leq 10^{6}$

NOTE Use Fast I/O