Let us denote by d(n) the sum of all divisors of the number n, i.e. d(n) = ∑_{k | n} k.

For example, d(1) = 1, d(4) = 1+2+4=7, d(6) = 1+2+3+6=12.

For a given number c, find the minimum n such that d(n) = c.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

Each test case is characterized by one integer c (1 ≤ c ≤ 10^7).

Output

For each test case, output: 

  * "-1" if there is no such n that d(n) = c; 
  * n, otherwise. 

Example

Input


12
1
2
3
4
5
6
7
8
9
10
39
691


Output


1
-1
2
3
-1
5
4
7
-1
-1
18
-1
#------------------Important Modules------------------#
from sys import stdin,stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
from random import *
input=stdin.readline
prin=stdout.write
from random import sample
from collections import Counter,deque
from fractions import *
from math import sqrt,ceil,log2,gcd,cos,pi
#dist=[0]*(n+1)
mod=10**9+7
mod2=998244353
"""
class DisjSet: 
    def __init__(self, n): 
        
        self.rank = [1] * n 
        self.parent = [i for i in range(n)] 
    def find(self, x): 
        if (self.parent[x] != x): 
              
             

            self.parent[x] = self.find(self.parent[x]) 
              
            
        return self.parent[x] 
  
  
    
    def union(self, x, y): 
          
         
        xset = self.find(x) 
        yset = self.find(y) 
  
        if xset == yset: 
            return
  
        if self.rank[xset] < self.rank[yset]: 
            self.parent[xset] = yset 
  
        elif self.rank[xset] > self.rank[yset]: 
            self.parent[yset] = xset 
  
        else: 
            self.parent[yset] = xset 
            self.rank[xset] = self.rank[xset] + 1
  

"""


        
def ps(n):
    cp=0;lk=0;arr={}
    lk=0;ap=n
    cc=0
    while n%2==0:
        n=n//2
        cc=1
    if cc==1:
        lk+=1
        
    
    
    
        
    for ps in range(3,ceil(sqrt(n))+1,2):
        #print(ps)
        cc=0
        while n%ps==0:
            n=n//ps
            cc=1

        lk+=1 if cc==1 else 0
        
            
            
    if n!=1:
        lk+=1
    
    if lk==1:    
        return [False,0]
        
    
    #print(arr)
    
    return [True,lk]


#count=0
#dp=[[0 for i in range(m)] for j in range(n)]
#[int(x) for x in input().strip().split()]
def gcd(x, y): 
      
    while(y): 
        x, y = y, x % y 
      
    return x 
          
# Driver Code         
def factorials(n,r):
    #This calculates ncr mod 10**9+7
    slr=n;dpr=r
    qlr=1;qs=1
    mod=10**9+7
    
    for ip in range(n-r+1,n+1):
        qlr=(qlr*ip)%mod
    for ij in range(1,r+1):
        qs=(qs*ij)%mod
    #print(qlr,qs)
    ans=(qlr*modInverse(qs))%mod
    return ans

        
        
def modInverse(b):
    qr=10**9+7
    return pow(b, qr - 2,qr)

#===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func
def power(arr):
  listrep = arr
  subsets = []
  for i in range(2**len(listrep)):
    subset = []
    for k in range(len(listrep)):            
      if i & 1<<k:
        subset.append(listrep[k])
    subsets.append(subset)        
  return subsets
def pda(n) :
    list=[];su=0
    for i in range(1, int(sqrt(n) + 1)) :
         if (n % i == 0) :
            if (n // i == i) :
                list.append(i)
                su+=i
            else :
                list.append(n//i);list.append(i)
                su+=i;su+=n//i
    # The list will be printed in reverse    
    return su
def dis(xa,ya,xb,yb):
    return sqrt((xa-xb)**2+(ya-yb)**2)
#### END ITERATE RECURSION ####

 
#===============================================================================================
#----------Input functions--------------------#
def ii():
    return int(input())
def ilist():
    return [int(x) for x in input().strip().split()]
def islist():
    return list(map(str,input().split().rstrip()))
def inp():
    return input().strip()
def google(test,ans):
    return "Case #"+str(test)+": "+str(ans);
def overlap(x1,y1,x2,y2):
    if x2>y1:
        return y1-x2
    if y1>y2:
        return y2-x2
    return y1-x2;


###-------------------------CODE STARTS HERE--------------------------------###########

        
    

def dist(x1,y1,x2,y2):
    return sqrt((x1-x2)**2+(y1-y2)**2)
def sieve(n):
    ans=[i+1 for i in range(n+1)]
    prime = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):
        #ans[p]+=p;
 
        if (prime[p] == True):
            #ans[p]=p;
 
            for i in range(p * p, n+1, p):
                prime[i] = False
                
                ans[i]+=p
                if i//p!=p:
                    ans[i]+=i//p
        p += 1
    #print(ans[18])
    #ans=[i+1 for i in ans]
    ans[0]=0;ans[1]=1
    dicts={}
    for j in range(n+1):
        dicts[ans[j]]=j
 
    #ans=[]
    
    return dicts
        
            
def prod(arr):
    n=len(arr)
    k=1
    for j in range(n):
        k*=arr[j]
    return k
        
    
#########################################################################################
t=int(input())
#t=1
#ans=sieve(10**7)
n=10**7
ans=[i+1 for i in range(n+1)]
prime = [True for i in range(n+1)]
p = 2
while (p * p <= n):
        #ans[p]+=p;
 
    if (prime[p] == True):
            #ans[p]=p;
 
        for i in range(p * p, n+1, p):
            prime[i] = False
                
            ans[i]+=p
            if i//p!=p:
                ans[i]+=i//p
    p += 1
    #print(ans[18])
    #ans=[i+1 for i in ans]
ans[0]=0;ans[1]=1
dicts=[-1]*(10**7+1)
for j in range(n+1):
    if ans[j]<=10**7:
        dicts[ans[j]]=j

for p in range(t):
    c=ii()
    #ks=bl(ans,c,0,10**6+1)
    #print(ans[18])
    
    
    
    print(dicts[c])
    
        
    
                
        
    
                
                
                
        
        
        
        
        
        
            
        
    
    
    
    
        
            
            
        
    
    
                
        
    
    
        
    
            
        
            
            
            
        
        
        
    
            
        
        
    
            
    
                
                
    
                    
                    
                    
        
        
    
        
            
            
                
        
            
        
    
            
        
    
    
        
            
        
    
        
        
            
        
        
        
        
        
        
        
            
    
    
            
            
            
        
    
                
    
                
        
            
            
                
            
        
        

        
    
            
            
            
        
        
        

    
            
            
    
        
    
    
            
        
    
    
            
    
        
    
            
                
    
        
    
        
        
        
        
        
                
                
        
        
    
            
        
    
        
        
    
    
            
            
        
    
            
            
                
                
                
            
    
    
            
                
        
                
        
    
    
    
            
            
            
        
            
        
        
        
    
    
        
        
                
            
        
        
        
                
                
                
        
    
        
                
            
                
            
        
        
        
    
    
                
                
        
    
        
        
    
        
    
    
    
    
    
        
                
    
            
            
    
    





















    
