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
import bisect
import math

def isSquare(n):
    ## Trivial checks
    if type(n) != int:  ## integer
        return False
    if n < 0:  ## positivity
        return False
    if n == 0:  ## 0 pass
        return True

    ## Reduction by powers of 4 with bit-logic
    while n & 3 == 0:
        n = n >> 2

    ## Simple bit-logic test. All perfect squares, in binary,
    ## end in 001, when powers of 4 are factored out.
    if n & 7 != 1:
        return False

    if n == 1:
        return True  ## is power of 4, or even power of 2

    ## Simple modulo equivalency test
    c = n % 10
    if c in {3, 7}:
        return False  ## Not 1,4,5,6,9 in mod 10
    if n % 7 in {3, 5, 6}:
        return False  ## Not 1,2,4 mod 7
    if n % 9 in {2, 3, 5, 6, 8}:
        return False
    if n % 13 in {2, 5, 6, 7, 8, 11}:
        return False

        ## Other patterns
    if c == 5:  ## if it ends in a 5
        if (n // 10) % 10 != 2:
            return False  ## then it must end in 25
        if (n // 100) % 10 not in {0, 2, 6}:
            return False  ## and in 025, 225, or 625
        if (n // 100) % 10 == 6:
            if (n // 1000) % 10 not in {0, 5}:
                return False  ## that is, 0625 or 5625
    else:
        if (n // 10) % 4 != 0:
            return False  ## (4k)*10 + (1,9)

    ## Babylonian Algorithm. Finding the integer square root.
    ## Root extraction.
    s = (len(str(n)) - 1) // 2
    x = (10 ** s) * 4

    A = {x, n}
    while x * x != n:
        x = (x + (n // x)) >> 1
        if x in A:
            return False
        A.add(x)
    return True


pows = set()

for i in range(2, pow(10, 6) + 1):
    if isSquare(i):
        continue
    for j in range(3, 61, 2):
        p = pow(i, j)
        if p > 1e18:
            break
        pows.add(p)

pows = sorted(list(pows))

q = int(input())
for i in range(q):
    res = 0
    l, r = map(int, input().split())
    left = bisect.bisect_left(pows, l)
    right = bisect.bisect_left(pows, r)

    res += right - left
    if pows[right] == r:
        res += 1

    rootl = int(math.sqrt(l))
    rootr = int(math.sqrt(r))
    res += rootr - rootl
    if rootr*rootr == r:
        res += 1
    print(res)