You're given *Q* queries of the form (*L*, *R*). 

For each query you have to find the number of such *x* that *L* ≤ *x* ≤ *R* and there exist integer numbers *a* &gt; 0, *p* &gt; 1 such that *x* = *a*<sup class="upper-index">*p*</sup>.
The first line contains the number of queries *Q* (1 ≤ *Q* ≤ 10<sup class="upper-index">5</sup>).

The next *Q* lines contains two integers *L*, *R* each (1 ≤ *L* ≤ *R* ≤ 10<sup class="upper-index">18</sup>).
In query one the suitable numbers are 1 and 4.
6
1 4
9 9
5 7
12 29
137 591
1 1000000
2
1
0
3
17
1111
20
862 928
758 964
541 789
622 943
328 900
14 764
217 972
461 847
442 468
900 986
518 529
938 993
549 851
690 944
484 601
320 910
98 868
816 915
765 880
551 770
1
4
5
6
14
32
20
9
0
2
1
1
6
4
4
15
26
2
2
4
q=int(input())
def root(x,n):
    l=0
    r=x
    while(r-l>1):
        mid=(r+l)//2
        if(mid**n>x):
            r=mid
        else:
            l=mid
    return l

def calc(x):
    if(x==0):
        return 1
    dp=[0]*100
    sm=0
    for i in range(62):
        j=63-i
        dp[j]=root(x,j)
        for m in range(2,1000):
            if(j*m>63):
                break
            dp[j]-=dp[j*m]
        sm+=dp[j]
    return sm

for i in range(q):
    l,r=map(int,input().split())
    print(calc(r)-calc(l-1))