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.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.*;
import java.math.*;
public class Solution 
{ 
	static int dp[] ;
	static int least_prime[] ;
	static int least_prime_pow[] ;
	static long sigma[] ;
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
  
    public static void main(String[] args) 
    { 
        FastReader s=new FastReader();
        sigma =  new long[10000001];
        dp = new int[10000001];
        least_prime =  new int[10000001];
		
        least_prime_pow =  new int[10000001];

		calculateSmallestFactor(10000000);
		
		for(int i=1;i<=10000000;i++)
		{
			dp[i] = Integer.MAX_VALUE;
			sigma[i] = -1L;
		}
		sigma[1] = 1L;
		for(int i=1;i<=10000000;i++)
		{
			long ans = C(i);
			if(ans<=10000000L)
				dp[(int)ans] = Math.min(i,dp[(int)ans]);
		}
		
        int T = s.nextInt(); 
		while(T-->=1)
		{
			int x = s.nextInt();
			if(dp[x]!=Integer.MAX_VALUE)
				System.out.println(dp[x]);
			else
				System.out.println(-1);
		}
    } 
	static long C(int num)
	{
		
		if(sigma[num]!=-1L)
			return sigma[num];
		
		int y = (int)Math.pow(least_prime[num],least_prime_pow[num]);
		if(y==num)
		{
			int lps = least_prime[num];
			int e = least_prime_pow[num];
			sigma[num] = ((long)Math.pow(lps,e+1) - 1L)/(lps-1L);
		}
		else
			sigma[num] = C(y)*C(num/y);
		return sigma[num];
	}
	static void calculateSmallestFactor(int n)
	{
		Arrays.fill(least_prime,0);
		least_prime[1] = 1;
        for (int i = 2; i <= n; i++)
        {
             
            
            if (least_prime[i] == 0)
            {
                 
                
                least_prime[i] = i;
                for (long j = (long)i*i; j <= (long)n; j += (long)i)
                {
					if (least_prime[(int)j] == 0)
                        least_prime[(int)j] = i;
				}
            }
        }
		for(int i=2;i<=n;i++)
		{
			int temp = i;
			int count=0;
			int d = least_prime[i];
			while(temp%d==0)
			{
				count++;
				temp = temp/d;
			}
			least_prime_pow[i] = count;
		}
	}
	
 
}