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.*;
import java.io.File;  // Import the File class
import java.io.FileNotFoundException;  // Import this class to handle errors
import java.util.Scanner; 
public class Main  {
	
	
	  public static void main(String args[])throws Exception
	    {
		  BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
	        int t = Integer.parseInt(file.readLine());
	        int max = (int)1e7;
	        int[] d = new int[max+1];
	        int[] ans = new int[max+1];
	        Arrays.fill(ans, -1);
	        for (int i=1; i<=max; i++){
	            for (int j=i; j<=max; j += i){
	                // Add myself as the divsor of the multiples of me
	                d[j] += i;
	            }
	            if (d[i] <= max && ans[d[i]] == -1){
	                ans[d[i]] = i;
	            }
	        }
	        for (int q=0; q<t; q++){
	            int c = Integer.parseInt(file.readLine());
	            System.out.println(ans[c]);
	        }
	        
	}
	  
	  void solve()
	  {
		  int n=4;
		  int c=15	;
		  
		  int a[]={1,3,10,11};
		  int b[]={1,2,7};
		  int rem=0;
		  int res=Integer.MAX_VALUE;
		  int rem1=0;
		  int j=0;
		  int tot=0;
		  for(int i=0;i<a.length;i++)
		  {
			  rem=rem1;
			  int i1=0;
			  while(rem<c)
			  {
				  rem+=a[i];
				  i1++;
			  }
			  res=Math.min(res, i1+tot);
			  if(i==n-1) 
              	break;
			  
			  
			   j=0;
			  rem1=0;
			  while(rem1<b[i])
			  {
				  rem1+=a[i];
				  j++;
			  }
			  tot+=j;
			  tot++;
			  rem1+=tot*a[i];
			  rem1-=b[i];
			  System.out.print("s");
		  }
		  System.out.print(res);
	  }
	
	  
	
}