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 {
    public static void main(String[] args) {
        G a = new G();
        a.solve(System.in, System.out);
    }

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

        BigLongArray divisors = getDivisors(10_000_000L);
        BigLongArray precomputed = precompute(10_000_000L, divisors);

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

        writer.close();
    }

    public long solve(long n, BigLongArray precomputed) {
        long precomputedResult = precomputed.get(n);
        if (precomputedResult == 0) {
            return -1;
        } else {
            return precomputedResult;
        }
    }

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

    public BigLongArray precompute(long max, BigLongArray divisor) {
        BigLongArray result = new BigLongArray(max + 1);

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

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

        return res;
    }

    public static class BigLongArray {
        private final long[][] inner;

        private static final int SHIFT_LEFT = 16;
        private static final int MAX_INNER = 1 << SHIFT_LEFT;
        private static final int MASK = (1 << SHIFT_LEFT) - 1;

        public BigLongArray(long size) {
            inner = new long[(int) (size / MAX_INNER) + 1][MAX_INNER];
        }

        public long get(long index) {
            return inner[(int) (index >> SHIFT_LEFT)][(int) (index & MASK)];
        }

        public void set(long index, long value) {
            inner[(int) (index >> SHIFT_LEFT)][(int) (index & MASK)] = value;
        }
    }

    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());
        }
    }
}