table = [x for x in range(1000001)]

i = 2
while(i <= len(table)//2):
	j = 2*i
	while(j < len(table)):
		table[j] = table[j]*i
		#print(i,j)
		j = j+i
	i = i + 1

lookup = dict()

for n, x in enumerate(table):
	#print(i ,end=" ")
	lookup[x] = n

T = int(input())
while T > 0:
	X = int(input())
	try:
		print(lookup[X])
	except:
		print(-1)
	T = T -1