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

public class CodeForces {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		int n = 10000000;
		int[] s = new int[n+1];
		  
	    // Filling values in s[] using sieve
	    sieveOfEratosthenes(n, s);
	    
  	    long divSum[] = new long[n+1]; 
  	    int ans[] = new int[n+1];
  	    Arrays.fill(ans, -1);
	    for(int i=n; i>0; i--) {
	    	divSum[i] = generatePrimeFactors(i, s);
	    	if(divSum[i]<=n && divSum[i]>0) {
	    		ans[(int)divSum[i]] = i;
	    	}
	    }
	    	
		int t = Integer.parseInt(br.readLine().trim());
		while(t --> 0){
			int c = Integer.parseInt(br.readLine().trim());
			System.out.println(ans[c]);
		}
	}
	
	
	
	static void sieveOfEratosthenes(int N, 
            int s[])
	{
		// Create a boolean array 
		// "prime[0..n]"  and initialize
		// all entries in it as false.
		boolean[] prime = new boolean[N + 1];

		// Initializing smallest 
		// factor equal to 2
		// for all the even numbers
		for (int i = 2; i <= N; i += 2)
		s[i] = 2;
		
		// For odd numbers less 
		// then equal to n
		for (int i = 3; i <= N; i += 2)
		{
		if (prime[i] == false)
		{
		// s(i) for a prime is
		// the number itself
		s[i] = i;
		
		// For all multiples of 
		// current prime number
		for (int j = i; (long)j * i <= N; j += 2)
		{
		if (prime[i * j] == false)
		{
		prime[i * j] = true;
		
		// i is the smallest prime 
		// factor for number "i*j".
		s[i * j] = i;
		}
		}
		}
		}
		}
	

	static long generatePrimeFactors(int N, int[] s)
	{
		long res = 1;	    
	    long curr = s[N]; // Current prime factor of N
	    long p = curr*curr;
	  
	    // Printing prime factors 
	    // and their powers
	    while (N > 1)
	    {
	        N /= s[N];
	  
	        // N is now N/s[N]. If new N 
	        // also has smallest prime 
	        // factor as curr, increment power
	        if (curr == s[N])
	        {
	        	p *= curr;
	            continue;
	        }
	  
        	res *= (p-1)/(curr-1);
	  
	        // Update current prime factor 
	        // as s[N] and initializing
	        // count as 1.
	        curr = s[N];
	        p = curr*curr;
	    }
	    return res;
	}
	
}