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.util.*;
import java.util.Map.Entry;

import java.math.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {
		InputReader in = new InputReader(System.in);
		// Scanner in = new Scanner(System.in);
		// Scanner in = new Scanner(new BufferedReader(new
		// InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(System.out);
		// InputReader in = new InputReader(new
		// File("ethan_traverses_a_tree.txt"));
		// PrintWriter out = new PrintWriter(new
		// File("ethan_traverses_a_tree-output.txt"));

		long[] d = getd();

		Map<Long, Integer> ans = new HashMap<Long, Integer>();
		int t = in.nextInt();
		long[] query = new long[t];
		for (int i = 0; i < t; i++) {
			long q = in.nextInt();
			query[i] = q;

			ans.put(q, -1);
		}

		for (int i = 1; i < d.length; i++) {
			long k = d[i];
			if (ans.containsKey(k) && ans.get(k) == -1) {
				ans.put(k, i);
			}
		}

		for (int i = 0; i < t; i++) {
			out.printf("%d\n", ans.get(query[i]));
		}

		out.close();
	}

	static public long[] getd() {
		int maxn = 10000000;

		int[] lastprime = new int[maxn];
		for (int i = 2; i * i < maxn; i++) {
			if (lastprime[i] == 0) {
				for (int j = i * i; j < maxn; j = j + i) {
					if (lastprime[j] == 0) {
						lastprime[j] = i;
					}
				}
			}
		}

		for (int i = 2; i < maxn; i++) {
			if (lastprime[i] == 0) {
				lastprime[i] = i;
			}
		}

		int[] multi = new int[maxn];
		int[] primemulti = new int[maxn];
		for (int i = 2; i < maxn; i++) {
			int k = lastprime[i];
			int next = i / k;
			if (lastprime[next] == k) {
				multi[i] = multi[next] * k + k;
				primemulti[i] = primemulti[next] * k;
			} else {
				multi[i] = k;
				primemulti[i] = k;
			}
		}

		long[] d = new long[maxn];
		d[1] = 1;
		for (int i = 2; i < maxn; i++) {
			int k = primemulti[i];
			d[i] = d[i / k] + d[i / k] * multi[i];
		}

		for (int i = 0; i < 50; i++) {
			//System.out.printf("%d %d\n", i, d[i]);
		}

		return d;
	}

	static class InputReader {
		BufferedReader br;
		StringTokenizer st;

		public InputReader(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public InputReader(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		public boolean hasNext() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return false;
				st = new StringTokenizer(s);
			}
			return true;
		}

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

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

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