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.
import math
def count(x, y):
    z = [1] * ( y  - x + 1)

    for i in range(2, int(math.sqrt(y)) + 1):
        step = i ** 2
        if x % step == 0: j = x
        else: j = x + step - (x%step)

        while(j <= y):
            z[j - x] = 0
            j += step

    return z.count(1)
       
def get():
    t = int(raw_input())
    for i in range(t):
        s = raw_input().split()
        x, y = int(s[0]), int(s[1])
        if x > y: x, y = y, x
        print count(x, y)

if __name__=="__main__":
    get()