Problem: 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

Solution (in JAVA):

Solution:
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class G_my_2 {
    public static void main(String[] args) {
        new G_my_2().solve(System.in, System.out);
    }

    private long[] precomputed;

    public void precompute() {
        long[] divisors = getDivisors(10_000_000L);
        precomputed = precompute(10_000_000L, divisors);
    }

    public void solve(InputStream in, OutputStream out) {
        InputReader inputReader = new InputReader(in);
        PrintWriter writer = new PrintWriter(new BufferedOutputStream(out));

        precompute();

        int t = inputReader.nextInt();
        for (int t1 = 0; t1 < t; t1++) {
            long n = inputReader.nextLong();
            writer.println(solve(n));
        }

        writer.close();
    }

    public long solve(long n) {
        long precomputedResult = precomputed[(int) n];
        if (precomputedResult == 0) {
            return -1;
        } else {
            return precomputedResult;
        }
    }

    public long[] getDivisors(long max) {
        long[] divisor = new long[(int) max + 1];
        for (int i = 2; i <= max; i++) {
            divisor[i] = i;
        }
        long maxSqrt = (long) Math.sqrt(max) + 1;
        for (long i = 2; i <= maxSqrt; i++) {
            if (divisor[(int) i] != i) {
                continue;
            }
            long j = i * i;
            while (j <= max) {
                divisor[(int) j] = i;
                j += i;
            }
        }
        return divisor;
    }

    public long[] precompute(long max, long[] divisor) {
        long[] result = new long[(int) max + 1];

        for (long l = 10_000_000L; l >= 1; l--) {
            long sumOfDivisors = sumOfDivisors(l, divisor);
            if (sumOfDivisors <= max) {
                result[(int) sumOfDivisors] = l;
            }
        }
        return result;
    }

    public long sumOfDivisors(long number, long[] divisor) {
        long res = 1;
        while (number > 1) {
            long primeDivisor = divisor[(int) number];
            long sum = 0;
            long test = 1;
            do {
                number /= primeDivisor;
                test *= primeDivisor;
                sum += test;
            } while (number % primeDivisor == 0);
            res *= (1 + sum);
        }

        return res;
    }

    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}