def f(a):
  #L[a]は何番目か
  k=L[a]
  return a+1+int(k**0.5)
T=int(input())
n=10**18
L=set()
for i in range(1,(10**6+1)):
  if int(i**0.5)**2==i:
    continue
  for s in range(3,65,2):
    if pow(i,s)>n:
      break
    else:
      L.add(pow(i,s))
L=list(L)
L.sort()
for i in range(T):
  K=int(input())
  if K==1:
    print(1)
    continue
  if K==2:
    print(4)
    continue
  
  sita=0
  ue=1003331
  for j in range(100):
    this=(sita+ue)//2
    if f(this)>K:
      ue=this
    else:
      sita=this
    if ue-sita<=1:
      if f(ue)==K:
        print(L[ue])
        break
      if f(sita)==K:
        print(L[sita])
        break
      s=K-f(sita)
      a=L[sita]
      n=int(a**0.5)
      print((n+s)**2)
      break