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.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {

	static int MAX_PRIME = 10000;
	static int sieve[] = new int[MAX_PRIME];
	static int prime[] = new int [1229];
	static int cnt_prime;
	
	static TreeMap<Integer, ArrayList<Integer>> map = new TreeMap<>();
	static void put(int dp, int mult) {
		ArrayList<Integer> list = map.get(dp);
		if (list == null) list = new ArrayList<>();
		list.add(mult);
		map.put(dp, list);
	}
	
	static int sz;
	static int dp[];
	static ArrayList<Integer> multiplier[];
	static ArrayList<Integer> origin_multiplier[];
	
	static {
		Arrays.fill(sieve, 0);
		for(int i = 2; i < MAX_PRIME; i++) {
			if (sieve[i] != 0) continue;
			prime[cnt_prime++] = i;
			int p = i * i;
			while(p < MAX_PRIME) {
				sieve[p] = prime[cnt_prime-1];
				p += i;
			}
		}
		put(1, 1);
		for(int i = 0; i < cnt_prime; i++) {
			int p = prime[i];
			int dp = p + 1;
			while(dp < MAX_PRIME) {
				if(map.containsKey(dp)) {
				}
				put(dp, p);
				p  *= prime[i];
				dp += p;
			}
		}
		sz = map.size();
		dp = new int[sz];
		multiplier = new ArrayList[sz];
		origin_multiplier = new ArrayList[sz];
		sz = 0;
		for(Entry<Integer,ArrayList<Integer>> entry : map.entrySet()) {
			dp[sz] = entry.getKey();
			multiplier[sz] = entry.getValue();
			origin_multiplier[sz] = new ArrayList<Integer>();
			for (int val : multiplier[sz]) {
				int orig = sieve[val];
				if (orig == 0) orig = val;
				origin_multiplier[sz].add(orig);
			}
			sz++;
		}
//		System.err.println(cnt_prime);
	}
	

	int used[] = new int[100];
	private int solve(int n, int min_prime_index_used, int depth) {
//		System.out.println("enter " + n + " " + depth);

		{
			int p = get_prime_1(n);
			if (p != -1) {
				boolean ok = true;
				for (int z = 0; z < depth; z++) {
					ok &= used[z] != p;
			    }
			    if (ok) {
//			    	System.out.println("Found 1: " + n + "<-" + p + " || "+ used[0]);
			    	return p;
			    }
			}
		}
		{
			int p = get_prime_2(n, depth);
			if (p != -1) {
//				System.out.println("Found 2: " + n + "<-" + p);
				return p;
			}
		}
//		System.err.println(n);
//		System.err.println(Arrays.toString(dp));
		for (int i = min_prime_index_used - 1; i >= 0; i--) {
			if (n % dp[i] == 0) {
//				System.out.println("consider " + i + " " + dp[i] + " | " + depth);
				for (int j = 0; j < multiplier[i].size(); j++) {
					int mult = multiplier[i].get(j);
					int orig_mult = origin_multiplier[i].get(j);
//					System.err.println("~~~ " + dp[i] + " " + multiplier[i] + " " + origin_multiplier[i]);
					boolean ok = true;
					for (int z = 0; z < depth; z++)
						ok &= used[z] != orig_mult;
					if (!ok) continue;
					used[depth] = orig_mult;
					int val = solve(n/dp[i], i, depth + 1);
					if (val != -1) return val * mult;
				}
			}
		}
		return -1;
	}	
	
	// x = p + 1
	private int get_prime_1(int x) {
		if (x == 1) return 1;
		x--;
		if (x < 2) return -1;
		for(int p : prime) {
			if (p == x) return x;
			if (p * p > x) return x;
			if (x % p == 0) return -1;
		}
		throw new RuntimeException("Err1");
	}

	// x = (p^k - 1) / p - 1
	private int get_prime_2(long x, int depth) {
		if (x < 2) return -1;
		for(int p : prime) {
			long y = x * (p - 1) + 1;
			long pp = p * p;
			if (y % pp != 0) continue;

			boolean ok = true;
			for (int z = 0; z < depth; z++) {
				ok &= used[z] != p;
		    }
			if (!ok) continue;
			
			while (y % pp == 0 && y != pp) pp *= p;
			if (y == pp) {
				return (int)(pp /p);
			}
		}
		return -1;
	}
	

	private void solve() throws Exception {
		int n = nextInt();
		out.println(solve(n, sz, 0));
	}


	void run() throws Exception {
		int cnt_test = nextInt();
		for (int test = 0; test < cnt_test; test++) {
			solve();
		}
	}


	public static void main(String[] args) throws Exception {
		Main instance = new Main();
		instance.initStreams();
		instance.run();
		instance.closeStreams();
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

	void initStreams() throws FileNotFoundException {
		if (new File("input.txt").exists()) {
			try {
				System.setIn(new FileInputStream("input.txt"));
			} catch (FileNotFoundException e1) {
				e1.printStackTrace();
			}
		}
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
	}

	void closeStreams() throws IOException {
		in.close();
		out.close();
	}

	String nextString() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextString());
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextString());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextString());
	}
}
