for _ in range(int(input())):
 k,n,o=int(input()),0,2**63
 while o-n>1:
  m,c=(o+n)//2,[0]*60
  for i in range(59,1,-1):
   N,O=int(2**(63/i))+1,0
   while N-O>1:
    M=(N+O)//2
    if M**i<=m:O=M
    else:N=M
   c[i]=O-1-sum(c[::i])
  if sum(c)+1>=k:o=m
  else:n=m
 print(o)