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.ArrayList;
import java.util.Arrays;
import java.util.List;
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));

        List<Long> primes = new ArrayList<>();
        BigLongArray divisors = getDivisors(10_000_000L, primes);
        BigLongArray precomputed = precompute(10_000_000L, divisors, primes);

        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, List<Long> primes) {
        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 <= max; i++) {
        for (long i = 2; i <= maxSqrt; i++) {
            if (divisor.get(i) != i) {
                continue;
            }
            primes.add(i);
            long j = i * i;
            while (j <= max) {
//                if (divisor.get(j) == j) {
                    divisor.set(j, i);
//                }
                j += i;
            }
        }
        return divisor;
    }

    public BigLongArray precompute(long max, BigLongArray divisor, List<Long> primes) {
        BigLongArray result = new BigLongArray(max + 1);
//        for (long l : primes) {
//            long sumOfDivisors = sumOfDivisors(l, divisor);
//            if (sumOfDivisors <= max) {
//                result.set(sumOfDivisors, l);
//            }
//        }

        long numberForMaxResult = 0;
//        for (long l = 1; l <= 10_000_000L; l++) {
//            long sumOfDivisors = sumOfDivisors(l, divisor);
//            if (sumOfDivisors <= max) {
//                long currentResult = result.get(sumOfDivisors);
//                if (currentResult == 0L || l < currentResult) {
//                    result.set(sumOfDivisors, l);
////                    if (l > numberForMaxResult && !primes.contains(l)) {
////                        numberForMaxResult = l;
////                    }
//                }
//            }
//        }

        for (long l = 10_000_000L; l >= 1; l--) {
            long sumOfDivisors = sumOfDivisors(l, divisor);
            if (sumOfDivisors <= max) {
                result.set(sumOfDivisors, l);
            }
        }
//        System.out.println("Number for max result: " + numberForMaxResult);
        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 MAX_INNER = 65_536;

        private static final int shiftLeft = 16;
        private static final int mask = (1 << shiftLeft) - 1;

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

        public long get(long index) {
//            return inner[(int) (index / MAX_INNER)][(int) (index % MAX_INNER)];
            return inner[(int) (index >> shiftLeft)][(int) (index & mask)];
        }

        public void set(long index, long value) {
//            inner[(int) (index / MAX_INNER)][(int) (index % MAX_INNER)] = value;
            inner[(int) (index >> shiftLeft)][(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());
        }
    }
}