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
"""Problem C - Sad powers.

http://codeforces.com/contest/955/problem/C

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 = ap.

Input:

The first line contains the number of queries Q (1 ≤ Q ≤ 105).

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

Output:

Output Q lines — the answers to the queries.

"""
import math
import logging

ch = logging.StreamHandler()
ch.setLevel(logging.DEBUG)

logger = logging.getLogger()
logger.setLevel(logging.DEBUG)
logger.addHandler(ch)


def solve(queries):
    # FIXME: Use sqrt decomposition
    data = preprocess(queries)
    res = []
    for l, u in queries:
        res.append(sum(data[x] for x in range(l, u + 1)))
    return res

# def single_factor(n):
#     if n == 1:
#         return True
#     a = 2
#     while True:
#         p = math.log(n, a)
#         if p < 2:
#             return False
#         if p % 1 == 0:
#             return True
#         a += 1
#     return False


def single_factor(n):
    def check(x, y):
        factors = 0
        while x > 1 and x % y == 0:
            x //= y
            factors += 1
        logger.debug('%s - x=%s y=%s rem=%s', x == 1 and factors > 1, n, y, x)
        return x == 1 and factors > 1
    if n == 1:
        return True
    for i in range(2, int(n ** 0.5) + 1):
        if check(n, i):
            return True
    return False


def preprocess(queries):
    min_q, max_q = float('inf'), 0
    for l, u in queries:
        min_q = min(min_q, l)
        max_q = max(max_q, u)
    # a = [0] * (max_q + 1)
    # for n in range(min_q, max_q + 1):
    #     a[n] = int(single_factor(n))
    # max_n = 10 ** 18
    max_n = max_q
    a = [0] * (max_n + 1)
    a[1] = 1
    for i in range(2, int(max_n ** 0.5) + 1):
        j = 2
        while i ** j <= max_n:
            a[i ** j] = 1
            j += 1
    return a


def main():
    queries = [[*map(int, input().split())] for _ in range(int(input()))]
    result = solve(queries)
    print(result)


if __name__ == '__main__':
    main()
