nakul-and-gold-coins

Nakul is on a Gold Island. In front of him are precious coins numbered 1 to 10^8 where each coin is in the form of a regular polygon with its number of sides equal to the number of distinct factors of the number. (Yes there is a coin with one side also. Its called a circle!). The value of each distinct factor is inscribed along each side.

His girlfriend, Sona, demands a very expensive gift on her birthday this year and so he plans to maximize his budget by stealing as many gold coins as he can. 

However there is a small problem. Due to the security installed on the island, he can only steal square coins. Also, since Sona does not like large numbers, he cannot take away coins where more than one of the sides has a value greater than 10^6.

Now at any point of time Nakul gets access to a range of coins numbered L to R(both inclusive). Help him tell the maximum number of coins he can take away from those coins.

Note: 1 and N are also counted as factors of N.

Input
First line has an integer T which is the number of test cases. 
T lines follow, each has 2 integers L and R which is the range.

Output
One integer per test case giving count of such numbers in the range.

Constraints
1 ≤ T ≤ 300
1 ≤ L ≤ R ≤ 10^8

Note
TimeLimit for this question is 3 times the setters/testers solution.

Note2
Any 3 sides taken together will be mutually co-prime.

SAMPLE INPUT
3
1 5
2 10
56 65

SAMPLE OUTPUT
0
2
4

Explanation

Case 1: 
No numbers in this range possible.

Case 2:
The numbers possible are 6, 10.
Distinct factors of 6 are 1, 2, 3, 6.
Distinct factors of 10 are 1, 2, 5, 10.

Case 3: 
The numbers possible are 57, 58, 62, 65.

Source: hackerearth | Difficulty: MEDIUM
Tags: Number theory

Sorting


Solutions: