With full zeal, Daenerys Targaryen is looking to conquer the seven kingdoms. In need of wise commanders, she wants them to solve the below problem:

Given the following function F and an integer N find the smallest integer x satisfying F(x) = N.

    function f(x) {
        ret = 0
        for d = 1..x:
            if (x mod d == 0) and
               (gcd(d, x/d) == 1):
                ret += d
        return ret
    }

If no such x exists, print “-1” (without quotes.)

Input

The first line contains one integer T, the number of times she gives you the problem.

T lines follow, each containing a single integer N.

Output

Print the answer for each problem on a separate line.

Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 10¹⁰

Example

Input:
4
5
4
9
7
Output:
4
3
8
-1