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: HARD
Tags: Number theory

Sorting

Mathematics
Skill types: Sorting

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
j = 2
while True:
	j2 = j * j
	i = j * j2
	if i >= big:
		break
	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())
out = []
for line in sys.stdin:
	(L, R) = line.split()
	L = int(L)
	R = int(R)
	a = -1
	b = len(pos)
	while b - a > 1:
		m = (a + b) // 2
		if pos[m] < L:
			a = m
		else:
			b = m
	under = a
	a = -1
	b = len(pos)
	while b - a > 1:
		m = (a + b) // 2
		if pos[m] <= R:
			a = m
		else:
			b = m
	upper = a
	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(1e+18 + 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')


import sys
readline = sys.stdin.buffer.readline
J = set()
for i in range(2000):
	J.add(i ** 2)
	J.add(i ** 3)
Ri = set()
for p in range(5, 61, 2):
	if p % 3 == 0:
		continue
	for base in range(2, 10 ** 9):
		if base in J:
			continue
		bp = pow(base, p)
		if bp > 10 ** 18:
			break
		Ri.add(bp)
Ri = list(Ri)
Ri.sort()
LL = len(Ri)

def calc(x):
	res = 0
	ng = 10 ** 9 + 1
	ok = 0
	while abs(ok - ng) > 1:
		med = (ok + ng) // 2
		if med * med <= x:
			ok = med
		else:
			ng = med
	res += ok
	ng = 10 ** 6 + 1
	ok = 0
	while abs(ok - ng) > 1:
		med = (ok + ng) // 2
		if med * med * med <= x:
			ok = med
		else:
			ng = med
	res += ok
	ng = 10 ** 3 + 1
	ok = 0
	while abs(ok - ng) > 1:
		med = (ok + ng) // 2
		if med * med * med * med * med * med <= x:
			ok = med
		else:
			ng = med
	res -= ok
	ng = LL
	ok = -1
	while abs(ok - ng) > 1:
		med = (ok + ng) // 2
		if Ri[med] <= x:
			ok = med
		else:
			ng = med
	res += ok + 1
	return res
Q = int(readline())
Ans = [None] * Q
for qu in range(Q):
	(L, R) = map(int, readline().split())
	Ans[qu] = calc(R) - calc(L - 1)
print('\n'.join(map(str, Ans)))