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.*;
import java.nio.CharBuffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class P1512G {

//    private static final int MAX = 10_000;
    private static final int MAX = 10_000_000;

    public static void main(String[] args) {
        var scanner = new SimpleScanner(System.in);
        var writer = new PrintWriter(System.out);

        var pFlag = new boolean[MAX + 1];
        var primes = new ArrayList<Integer>((int) (MAX / Math.log1p(MAX)) * 2);

        var ans = new long[MAX + 1];
        Arrays.fill(ans, -1);
        ans[1] = 1;

        var f = new long[MAX + 1];
        var g = new long[MAX + 1];
        g[1] = f[1] = 1;
        for (var i = 2; i <= MAX; ++i) {
            if (!pFlag[i]) {
                primes.add(i);
                f[i] = i + 1;
                g[i] = i + 1;
            }
            if (f[i] <= MAX && ans[(int) f[i]] == -1)
                ans[(int) f[i]] = i;
            for (var prime : primes) {
                if (prime * i > MAX)
                    break;
                pFlag[prime * i] = true;
                if (i % prime == 0) {
                    g[prime * i] = g[i] * prime + 1;
                    f[prime * i] = f[i] / g[i] * g[prime * i];
                    break;
                }
                f[prime * i] = f[i] * f[prime];
                g[prime * i] = prime + 1;
            }
        }

        var caseNum = scanner.nextInt();
        while (caseNum-- > 0) {
            var t = scanner.nextInt();
            writer.println(ans[t]);
        }


        writer.close();
    }

    private static class SimpleScanner {

        private static final int BUFFER_SIZE = 10240;

        private Readable in;
        private CharBuffer buffer;
        private boolean eof;

        private SimpleScanner(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
            buffer = CharBuffer.allocate(BUFFER_SIZE);
            buffer.limit(0);
            eof = false;
        }


        private char read() {
            if (!buffer.hasRemaining()) {
                buffer.clear();
                int n;
                try {
                    n = in.read(buffer);
                } catch (IOException e) {
                    n = -1;
                }
                if (n <= 0) {
                    eof = true;
                    return '\0';
                }
                buffer.flip();
            }
            return buffer.get();
        }

        private void checkEof() {
            if (eof)
                throw new NoSuchElementException();
        }

        private char nextChar() {
            checkEof();
            char b = read();
            checkEof();
            return b;
        }

        private String next() {
            char b;
            do {
                b = read();
                checkEof();
            } while (Character.isWhitespace(b));
            StringBuilder sb = new StringBuilder();
            do {
                sb.append(b);
                b = read();
            } while (!eof && !Character.isWhitespace(b));
            return sb.toString();
        }

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

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

        private double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}