Nakul is on a Gold Island. In front of him are precious coins numbered 1 to 108 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 106.
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 ≤ 108
Note TimeLimit for this question is 3 times the setters/testers solution.
Note2 Any 3 sides taken together will be mutually co-prime.