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 \le T \le 10\)
\(1 \le X,Y \le 10 ^ 9\)
\(0 \le |X-Y| \le 10^6\)