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 > 0, p > 1 such that x = a^{p}.


-----Input-----

The first line contains the number of queries Q (1 ≤ Q ≤ 10^5).

The next Q lines contains two integers L, R each (1 ≤ L ≤ R ≤ 10^18).


-----Output-----

Output Q lines — the answers to the queries.


-----Example-----
Input
6
1 4
9 9
5 7
12 29
137 591
1 1000000

Output
2
1
0
3
17
1111



-----Note-----

In query one the suitable numbers are 1 and 4.

Difficulty: interview

Starter code:

Solutions:
import sys

import math
from math import sqrt
import bisect
 
small = 10**5+1
big = 10**18+1
 
pos = []
f = pos.append
#pos.add(1)
j = 2
while True:
    #if sqrt(j).is_integer():
    #    j+=1
    #    continue
    j2 = j*j
    i = j*j2
    if i>=big:
        break
    #if int(i**0.5+0.5)**2==i:
    #    j+=1
    #    continue
    while i<big:
        f(i)
        i *= j2
    j += 1
pos2 = [p for p in pos if not sqrt(p).is_integer()]
pos2.sort()
prev = -1
pos = []
f = pos.append
for p in pos2:
    if p==prev:
        continue
    f(p)
    prev = p
 
 
 
q = int(input())
#inp = [int(x) for line in sys.stdin for x in line.split()]
#ii = 0
out = []
for line in sys.stdin:
    L,R = line.split()
    L = int(L)
    R = int(R)
    
 
    #ii+=2
    a = -1
    b = len(pos)
    
    
    while b-a>1:
        m = (a+b)//2
        if pos[m]<L:
            a=m
        else:
            b=m
    under = a
    #under = bisect.bisect_left(pos,L)
    #if under<len(pos) and pos[under]>=L:
    #    under -= 1
    
    a = -1
    b = len(pos)
    
    
    
    while b-a>1:
        m = (a+b)//2
        if pos[m]<=R:
            a = m
        else:
            b = m
    upper = a
    #upper = bisect.bisect_left(pos,R+1)-1
    Lupp = max(int(sqrt(L)-1),0)
    while Lupp*Lupp<L:
        Lupp+=1
    
    Rdown = int(sqrt(R))+1
    while Rdown*Rdown>R:
        Rdown-=1
 
    count = max(0,Rdown-Lupp+1)
    out.append(str(upper-under+count))
print('\n'.join(out))

import math
import bisect
import sys

def flrt(exp,x):
    l=max(0,math.floor(x**(1/exp))-3)
    
    r= math.floor(x**(1/exp))+3
    while l<r:
        mid=(l+r)//2
        if mid**exp<=x:
            l=mid+1
        else: 
            r=mid
    return l-1
   
    
def c1(r):
    ans=set()
    pr = [5,7,11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
    for i in pr:
        x=2
        while x**i <= r:
            val=x**i
            b2=flrt(2,val)
            b3=flrt(3,val)
            if b2**2 != val and b3**3 != val:
                ans.add(val)
            x+=1
    return ans
    
def solve(r, pc):
    if r==0:
        return 0
    
    a=[2,3]
    ans=0
    for i in range(1,2**len(a)):
        tot=0
        mult=1
        for j,x in enumerate(a):
            if i&(1<<j):
                mult*=x
                tot+=1
        d=  flrt(mult,r)      
        ans+= d if tot%2 else -d
        
    return ans + bisect.bisect_right(pc,r)    
       
    lp=0 
    rp=len(pc)
    while lp<rp:
        mid = (lp+rp)//2
        if pc[mid] <= r:
            lp = mid+1
        else:
            rp = mid
        
    
    return ans + lp
q = int(input())

pc= c1(1e18+1)


pca=list(pc)
pca.sort()
        
 
for i in range(q):
    l,r = [int(x) for x in sys.stdin.readline().split()]
    ans=solve(r,pca)-solve(l-1,pca)
    print(ans)


import math
import bisect
import sys

def flrt(exp,x):
    l=max(0,math.floor(x**(1/exp))-3)
    
    r= math.floor(x**(1/exp))+3
    while l<r:
        mid=(l+r)//2
        if mid**exp<=x:
            l=mid+1
        else: 
            r=mid
    return l-1
   
    
def c1(r):
    ans=set()
    pr = [5,7,11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
    for i in pr:
        x=2
        while x**i <= r:
            val=x**i
            b2=flrt(2,val)
            b3=flrt(3,val)
            if b2**2 != val and b3**3 != val:
                ans.add(val)
            x+=1
    return ans
    
def solve(r, pc):
    if r==0:
        return 0
    
    a=[2,3]
    ans=0
    for i in range(1,2**len(a)):
        tot=0
        mult=1
        for j,x in enumerate(a):
            if i&(1<<j):
                mult*=x
                tot+=1
        d=  flrt(mult,r)      
        ans+= d if tot%2 else -d
        
    return ans + bisect.bisect_right(pc,r)    
       
    lp=0 
    rp=len(pc)
    while lp<rp:
        mid = (lp+rp)//2
        if pc[mid] <= r:
            lp = mid+1
        else:
            rp = mid
        
    
    return ans + lp
q = int(input())

pc= c1(1e18+1)


pca=list(pc)
pca.sort()
        
 
for i in range(q):
    l,r = [int(x) for x in sys.stdin.readline().split()]
    ans=solve(r,pca)-solve(l-1,pca)
    sys.stdout.write(str(ans)+'\n')