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
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.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));

        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) {
//                if (divisor.get(j) == j) {
                    divisor.set(j, i);
//                }
                j += i;
            }
        }
        return divisor;
    }

    public static final List<Long> BIG_PRECOMP = Arrays.asList(5906061L, 4999168L, 4062400L, 3749844L, 3296340L);

    public BigLongArray precompute(long max, BigLongArray divisor) {
        BigLongArray result = new BigLongArray(max + 1);
        long numberForMaxResult = 0;
        long maxResult = 0;
        for (long l = 1; l <= 3296339L; l++) {
            long sumOfDivisors = sumOfDivisors(l, divisor);
            if (sumOfDivisors <= max) {
                if (result.get(sumOfDivisors) == 0L) {
                    result.set(sumOfDivisors, l);
//                    if (maxResult < sumOfDivisors) {
//                        maxResult = sumOfDivisors;
//                        numberForMaxResult = l;
//                    }
                }
            }
        }
//        System.out.println(numberForMaxResult);
        for (Long toPrecompute : BIG_PRECOMP) {
            result.set(sumOfDivisors(toPrecompute, divisor), toPrecompute);
        }
        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 = 2_000_000;

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

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