Game of numbers is a game where you are given two integers (X and Y), and you have to print the number of special numbers between X and Y both inclusive.
The property of a special numbers is as follows:
A special number is not divisible by any number of the form ZZ* where (Z\; >\; 1).

Input:
T, the number of test cases. Each test case consists of two space separated integers denoting X and Y.

Output:
The required answer in one line for each test case.

Constraints:
1 ≤ T ≤ 10
1 ≤ X,Y ≤ 10 ^ 9
0 ≤ |X-Y| ≤ 10^6

SAMPLE INPUT
1
1 10

SAMPLE OUTPUT
7

Explanation

In given test case, 4,8 and 9 are not special.

见题面

见题面