R=range
J=lambda:list(map(int,input().split()))
S=[set()for e in R(40)]
L=10**12
for e in R(2,40):
	for i in R(1,L):
		t=i**e
		if t<=L:S[e].add(t)
		else:break
for t in R(sum(J())):
	N,*_=J()
	a=1
	for e in R(39,1,-1):
		if N in S[e]:a=e;break
	print(a)