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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class G {
    private static int[] dp;
    static {
        int c = (int) Math.sqrt(10000000);
        dp = new int[c + 1];
        for (int i = 1; i <= c; i++) {
            dp[i] = i*dp[i];
        }
        
    }
    
    static void solve() {
        int t = readInt();
        while (t-- > 0) {
            int c = readInt();
            doSolve(c);
        }
    }

    private static void doSolve(int c) {
        if (c == 1) {
            out.println(1);
            return;
        }
        List<Integer> primes = primesBelow(c);
        Integer answer = minNumberWithDivisorSumOf(c, primes, 0, new HashMap<>());
        if (answer != null) {
            out.println(answer);
            return;
        }
        out.println(-1);
    }
    
    private static Integer minNumberWithDivisorSumOf(int c, List<Integer> primes, int prev_prime, Map<Integer, Integer> cache) {
        Integer n = cache.get(c);
        if (n != null) {
            return n;
        }
        for (int prime : primes) {
            if (prime <= prev_prime) {
                continue;
            }
            for (int power = 1, max_power = (int) (Math.log(c)/Math.log(prime)); power <= max_power; power++) {
                int part = (int) ((Math.pow(prime, power + 1) - 1)/(prime - 1));
                int number = (int) Math.pow(prime, power);
                if (part == c) {
                    cache.put(c, number);
                    return number;
                }
                if (c % part == 0) {
                    Integer rest = minNumberWithDivisorSumOf(c / part, primes, prime, cache);
                    if (rest != null) {
                        cache.put(c, number * rest);
                        return number * rest;
                    }
                }
            }
        }
        return null;
    }
    
    private static List<Integer> primesBelow(int n) {
        int[] lp = new int[n + 1];
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i < n; i++) {
            if (lp[i] == 0) {
                lp[i] = i;
                primes.add(i);
            }
            for (int j = 0; j < primes.size() && j <= lp[i] && i*primes.get(j) < n; j++) {
                lp[i*primes.get(j)] = primes.get(j);
            }
        }
        return primes;
    }

    //////////////////////// Template ////////////////////////
    static int readInt() {
        return Integer.parseInt(readString());
    }

    static long readLong() {
        return Long.parseLong(readString());
    }

    static String readString() {
        while (tok == null || !tok.hasMoreTokens()) {
            try {
                tok = new StringTokenizer(in.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tok.nextToken();
    }

    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;

    public static void main(String[] arg) {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
}
