Mehta woke up after a long sleep, and decided to attend college class which is infact pretty much unusual. But, to somehow survive this boring class, he asks his friend Verma, to give him a task which he would solve in that boring class. So, Mehta is given the following task.

He has to report the summation of all F(x) for x in range(A,B) where A and B are two given integers that is,

F(x) is defined as sum of powers of primes in prime factorization of x.

For Ex : - F(12) = 3
12 is written as 2^2 * 3^1, so powers are 2 and 1, Hence, F(12) = 2+1 = 3.

So, you being in the same condition as Mehta, decided to solve the same question in the class.

Input:
First Line of the input containts number of test cases T.
Next T lines of input consists of two space separated integers A and B as described in the above task.

Output:
Output the required summation of F(x) for all x in range(A,B) for each test case in a separate line.

Constraints:
A ≤ B
1 ≤ A,B ≤ 10^6
T ≤ 10^6

Note: Large Input/Output Files, use scanf/printf.

SAMPLE INPUT
4
2 4
4 7
2 56
43 2323

SAMPLE OUTPUT
4
6
124
6901

见题面

见题面