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$