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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class N713 {
	static PrintWriter out;
	static Scanner sc;
	static ArrayList<Integer>q,w;
	static ArrayList<Integer>adj[];
	static HashSet<Integer>primesH;
	static boolean prime[];
	//static ArrayList<Integer>a;
	static HashSet<Long>tmp;
	static boolean[]v;
	static int[]c,d;
	static int[][]dp;
	static char[][]mp;
	static int A,B,n,m,h,ans;
	static String a,b;
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
	//	A();
		//B();
	   // C();
		//D();
	//E();
		//F();
		G();
		out.close();
	}
	  private static void A() throws IOException {
		  int t=ni();
			while(t-->0) {
				int n=ni();
				int[]a=nai(n);
				int[]occ=new int[101];
				for(int i=0;i<a.length;i++) {
					occ[a[i]]++;
				}
				int num=-1;
				for(int i=0;i<occ.length;i++) {
					if(occ[i]==1) {
						num=i;
						break;
					}
				}
				int ans=-1;
				for(int i=0;i<n;i++) {
					if(a[i]==num) {
						ans=i+1;
						break;
					}
				}
				ol(ans);
			}
		
	   }
		static void B() throws IOException {
			int t=ni();
			while(t-->0) {
				int x1=-1,y1=-1,x2=-1,y2=-1;
				int n=ni();
				char[][]mp=new char[n][n];
				for(int i=0;i<n;i++) {
					mp[i]=ns().toCharArray();
				}
				for(int i=0;i<n;i++) {
					for(int j=0;j<n;j++) {
						if(mp[i][j]=='*') {
							if(x1==-1) {
								x1=i;y1=j;
							}else {
								x2=i;y2=j;
							}
						}
					}
				}
				int dx=Math.abs(x1-x2);
				int dy=Math.abs(y1-y2);
				int x3=-1,y3=-1,x4=-1,y4=-1;
				if(dx==0) {
					y3=y1;y4=y2;
					if(x1<n-1) {
						x3=x4=x1+1;
					}else {
						x3=x4=x1-1;
					}
				}else if(dy==0) {
					x3=x1;x4=x2;
					if(y1<n-1) {
						y3=y4=y1+1;
					}else {
						y3=y4=y1-1;
					}
				}else {
					x3=x1;x4=x2;y3=y2;y4=y1;
				}
				mp[x3][y3]='*';mp[x4][y4]='*';
				for(int i=0;i<n;i++) {
					for(int j=0;j<n;j++) {
						out.print(mp[i][j]);
					}
					ol("");
				}
			}
		}
		
		static void C() throws IOException{
			 int t=ni();
			 while(t-->0) {
				 int a=ni(),b=ni();
				 n=a+b;
				 char []c=ns().toCharArray();
				 int c1=0,c2=0;
				 boolean ok=true;
				 for(int i=0;i<c.length/2;i++) {
					 if(c[i]=='?'&&c[n-i-1]=='?')continue;
					 if(c[i]=='?') {
						 c[i]=c[n-i-1];
						 if(c[i]=='0')c1+=2;
						 else c2+=2;
					 }else if(c[n-i-1]=='?'){
						 c[n-i-1]=c[i];
						 if(c[i]=='0')c1+=2;
						 else c2+=2;
					 }else{
						 if(c[i]!=c[n-i-1]) {
							 ok=false;
							 break;
						 }
						 if(c[i]=='0')c1+=2;
						 else c2+=2;
					 }
				 }
				 if(c.length%2==1) {
					 if(c[c.length/2]!='?') {
						 if(c[c.length/2]=='0')c1++;
						 else c2++;
					 }
				 }
				 if(!ok||c1>a||c2>b) {
					 ol(-1);
				 }else {
					 int rema=a-c1,remb=b-c2;
					 if(c.length%2==0) {
						 if(rema%2==1||remb%2==1) {
							 ok=false;
						 }
					 }else {
						 if(rema%2==1&&c[c.length/2]=='1') {
							 ok=false;
						 }
						 if(remb%2==1&&c[c.length/2]=='0') {
							 ok=false;
						 }
					 }
					 if(!ok)ol(-1);
					 else {
						 for(int i=0;i<c.length/2;i++) {
							 if(c[i]=='?') {
							 if(rema>=2) {
								 c[i]=c[n-i-1]='0';
								 rema-=2;
							 }else{
								 c[i]=c[n-i-1]='1';
								 remb-=2; 
							 }
							 }
						 }
						 if(c.length%2==1&&c[c.length/2]=='?') {
							 if(rema==1) {
								 c[c.length/2]='0';
							 }else {
								 c[c.length/2]='1';
							 }
						 }
						 for(int i=0;i<c.length;i++) {
							 out.print(c[i]);
						 }
						 ol("");
					 }
				 }
			 }
		}
	static void E() throws IOException {
		int t=ni();
		while(t-->0) {
			int n=ni(),l=ni(),r=ni(),s=ni();
			boolean[]tk=new boolean[n+1];
			int len=r-l+1;
			int k=n-len;
			int max=((n*(n+1))/2)-((k*(k+1))/2);
			int min=(len*(len+1))/2;
			if(s>max||s<min) {
				ol(-1);
			}else {
				int cnd2[]=new int[len];
				for(int i=0;i<cnd2.length;i++) {
					cnd2[i]=n+i-len+1;
				}
				boolean ok=false;
				for(int i=0;i<cnd2.length;i++) {
					if(max-s<=cnd2[i]-i-1) {
						cnd2[i]-=(max-s);
						ok=true;
						break;
					}
					
					max-=(cnd2[i]-i-1);
					cnd2[i]=(i+1);
				}
				if(ok) {
					TreeSet<Integer>tr=new TreeSet<Integer>();
					for(int i=0;i<cnd2.length;i++) {
						tr.add(cnd2[i]);
						tk[cnd2[i]]=true;
					}
					for(int i=1,j=1;i<=n&&j<l;i++) {
						if(tr.contains(i))continue;
						tk[i]=true;
						out.print(i+" ");
						j++;
					}
					for(int x:tr) {
						out.print(x+" ");
					}
					for(int i=1,j=r+1;i<=n&&j<=n;i++) {
						if(tr.contains(i)||tk[i])continue;
						out.print(i+" ");
						j++;
					}
					ol("");
					
				}else {
					ol(-1);
				}
			}
			
		}
		
	}
	static void D() throws IOException {
		int t=ni();
		while(t-->0) {
			int n=ni();
			long[]a=nal(n+2);
			
			Arrays.sort(a);
			long sum=0;
			for(int i=0;i<=n;i++) {
				sum+=a[i];
			}
			boolean ok=false;
			int ex=-1;
			for(int i=0;i<n;i++) {
				sum-=a[i];
				if(sum==a[n+1]) {
					ok=true;
					ex=i;
					break;
				}
				sum+=a[i];
			}
			if(!ok) {
			sum-=a[n];
			if(sum==a[n+1]||sum==a[n]) {
				ex=n;
				ok=true;
			}
			}
			if(ok) {
				for(int i=0;i<=n;i++) {
					if(i!=ex)
						out.print(a[i]+" ");
				}
				ol("");
			}else {
				ol(-1);
			}
		
		}
	}
	static void F() throws IOException {
		int t=ni();
		while(t-->0) {
			int n=ni();
			int[][]a=new int[n][2];
			for(int i=0;i<n;i++) {
				a[i][0]=ni();
			}for(int i=0;i<n;i++) {
				a[i][1]=ni();
			}
			Arrays.sort(a,(u,v)->u[0]==v[0]?u[1]-v[1]:u[0]-v[0]);
			int cost=0;
			int r=1,c=1;
			for(int i=0;i<n;i++) {
				int cr=a[i][0],d1=cr-r;
				int cc=a[i][1],d2=cc-c;
				int num=d1-d2;
				if(r%2==c%2) {
					if(d1==d2)cost+=d1;
					else{
						cost+=(num/2);
					}
				}else if(d1!=d2) {
						cost+=((num+1)/2);
				}
				r=cr;
				c=cc;
				
			}
			out.println(cost);
		}
	}
	static void G() throws IOException {
		int t=ni();
		int lim=(int)1e7+1;
		int[]a=new int[lim];
		Arrays.fill(a, 1);
		for(int i=2;i<a.length;i++) {
			for(int j=i;j<a.length;j+=i) {
				a[j]+=i;
			}
		}
		int gt[]=new int[lim];
		for(int i=1;i<gt.length;i++) {
			if(a[i]<lim&&gt[a[i]]==0)gt[a[i]]=i;
		}
		while(t-->0) {
			int n=ni();
			int ans=gt[n];
			ol(ans==0?-1:ans);
		}
	}
	static int ni() throws IOException {
		return sc.nextInt();
	}
	static double nd() throws IOException {
		return sc.nextDouble();
	}
	static long nl() throws IOException {
		return  sc.nextLong();
	}
	static String ns() throws IOException {
		return sc.next();
	}
	static int[] nai(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		return a;
	}
	static long[] nal(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextLong();
		return a;
	}
	static int[][] nmi(int n,int m) throws IOException{
		int[][]a=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		return a;
	}

	static long[][] nml(int n,int m) throws IOException{
		long[][]a=new long[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextLong();
			}
		}
		return a;
	}
	static void o(String x) {
		out.print(x);
	}
	static void ol(String x) {
		out.println(x);
	}
	static void ol(int x) {
		out.println(x);
	}
	static void disp1(int []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public boolean hasNext() {return st.hasMoreTokens();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
			
		public boolean ready() throws IOException {return br.ready(); }
		

	}
}