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

public class Task{
        //  ..............code begins here..............

static long mod=(long)1e9+7,inf=(long)1e17;
static int[] spf;
static int[] sum;
static int[] dp;
static void pre(){
    spf=new int[10000001];
    sum=new int[10000001];
    dp=new int[10000001];
    for(int i=2;i*i<spf.length;i++){
        if(spf[i]!=0) continue;
        spf[i]=i;
        for(int j=i*i;j<spf.length;j+=i){
            if(spf[j]==0)spf[j]=i;
        }
    }
    for(int i=3000;i<spf.length;i++){
        if(spf[i]==0)spf[i]=i;
    }
    sum[1]=1;Arrays.fill(dp,(int)mod);
    dp[1]=1;
    for(int i=2;i<spf.length;i++){
        if(spf[i]==i)sum[i]=1+i;
        else{
            int x=1,j=i;
            while(j%spf[i]==0){
                j/=spf[i];x*=spf[i];
            }
            if(j==1)sum[i]=(int)Math.min(((long)i*spf[i]-1)/(spf[i]-1),(int)mod);
            else sum[i]=(int)Math.min((long)sum[x]*sum[i/x],(int)mod);
        }
        if(sum[i]<spf.length){
            dp[(int)sum[i]]=Math.min(dp[(int)sum[i]],i);
        }
    }
}
static void solve() throws IOException {
            int c=int_v(read());
            if(dp[c]==(int)mod)out.write("-1\n");
            else out.write(dp[c]+"\n");
}
//
public static void main(String[] args) throws  IOException{
                assign();
                int t=int_v(read()),cn=1;
                pre();
                while(t--!=0){
                    solve();cn++;
                }
                out.flush();
}

// taking inputs
static BufferedReader s1;
static BufferedWriter out;
static String read() throws IOException{String line="";while(line.length()==0){line=s1.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static void sort(int[] a){List<Integer> l=new ArrayList<>();for(int x:a){l.add(x);}Collections.sort(l);for(int i=0;i<a.length;i++){a[i]=l.get(i);}}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
static void assign(){s1=new BufferedReader(new InputStreamReader(System.in));out=new BufferedWriter(new OutputStreamWriter(System.out));}
//static String setpreciosion(double d,int k){BigDecimal d1 = new BigDecimal(Double.toString(d));return d1.setScale(k,RoundingMode.HALF_UP).toString();}//UP DOWN HALF_UP
static int add(int a,int b){int z=a+b;if(z>=mod)z-=mod;return z;}
static long gcd(long a,long b){if(b==0){return a;}return gcd(b,a%b);}
static long Modpow(long a,long p,long m){long res=1;while(p>0){if((p&1)!=0){res=(res*a)%m;}p >>=1;a=(a*a)%m;}return res%m;}
static long Modmul(long a,long b,long m){return ((a%m)*(b%m))%m;}
static long ModInv(long a,long m){return Modpow(a,m-2,m);}
//static long nck(int n,int r,long m){if(r>n){return 0l;}return Modmul(f[n],ModInv(Modmul(f[n-r],f[r],m),m),m);}
//static long[] f;
}