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
import sys

sys.setrecursionlimit(10**5)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.buffer.readline())
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def LI1(): return list(map(int1, sys.stdin.buffer.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
def BI(): return sys.stdin.buffer.readline().rstrip()
def SI(): return sys.stdin.buffer.readline().rstrip().decode()
# dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = 10**16
# md = 998244353
md = 10**9+7

from collections import defaultdict
from functools import lru_cache

mx=10**7+5

pp=[]
prime=[True]*mx
prime[1]=False
for a in range(2,mx):
    if prime[a]:
        pp.append(a)
        for b in range(a**2,mx,a):
            prime[b]=False

ps=defaultdict(lambda :inf)
for p in pp:
    s=1+p
    pw=p
    while s<mx:
        ps[s]=min(ps[s],pw)
        pw*=p
        s+=pw

@lru_cache(None)
def dfs(c,pre=1):
    # print(c,pre)
    res=inf
    if c in ps:res=ps[c]
    for d in range(pre+1,c+1):
        if d**2>=c:break
        if c%d:continue
        if d in ps:
            res=min(res,ps[d]*dfs(c//d,d))
    return res

for testcase in range(II()):
    c=II()
    if c==1:
        print(1)
        continue
    ans=dfs(c)
    if ans==inf:ans=-1
    print(ans)
