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
from collections import deque
import sys
input = sys.stdin.readline

x = [1] * 10000
pow107 = pow(10, 7)
p = []
y = []
z = []
for i in range(2, 10000):
    if x[i]:
        p.append(i)
        for j in range(i, 10000, i):
            x[j] = 0
        now, s = 1, 0
        y0 = set()
        while now <= pow107:
            s += now
            now *= i
            y0.add(s)
        y.append(y0)
        z.append(i)
l = len(p)

def prime_factorize(n):
    ans = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        c = 1
        while True:
            if n % i:
                break
            c *= i
            n //= i
        if c > 1:
            ans.append(c)
        if n == 1:
            break
    if not n == 1:
        ans.append(n)
    return ans

def is_Prime(i):
    if i == 2:
        return True
    if i % 2 == 0 or i == 1:
        return False
    s = int(i ** (1 / 2))
    while True:
        if s == 1:
            return True
        if i % s == 0:
            return False
        s -= 1

t = int(input())
for _ in range(t):
    c = int(input())
    if c == 1:
        ans = 1
        print(ans)
        continue
    if is_Prime(c - 1):
        ans = c - 1
        print(ans)
        continue
    s = deque(prime_factorize(c))
    ls = len(s)
    ans = 1
    for i in range(l):
        if not ls:
            break
        yi = y[i]
        for _ in range(ls):
            x = s.popleft()
            if x in yi:
                ls -= 1
                ans *= x - x // z[i]
                break
            s.append(x)
    if s:
        if s[0] > 10000:
            if is_Prime(s[0] - 1):
                ans *= s[0] - 1
                ls -= 1
    if ls:
        ans = -1
    print(ans)