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
{
    public static void main(String args[])throws Exception
    {
        FastInput fi=new FastInput(System.in);
        FastOutput fo=new FastOutput(System.out);
        int N=10000000,sum[]=new int[N+1],p[]=new int[N+1];
        sum[1]=1;
        int i,j;
        for(i=2;i<=N;i++)
        {
            sum[i]=Integer.MAX_VALUE;
            if(p[i]==0)
            for(j=i;j<=N;j+=i) p[j]=i;
        }

        for(i=2;i<=N;i++)
        {
            int x=i,sm=1,pr,c,mul;
            while(x!=1)
            {
                pr=p[x]; c=1; mul=1;
                while(x%pr==0)
                {
                    x/=pr;
                    mul*=pr;
                    c+=mul;
                }
                sm*=c;
            }
            if(sm<=N) sum[sm]=Math.min(sum[sm],i);
        }

        int t=fi.readInt();
        while(t-->0)
        {
            int n=fi.readInt();
            n=sum[n];
            if(n==Integer.MAX_VALUE) n=-1;
            fo.append(n+"\n");
        }
        fo.close();
    }

    static class FastInput
    {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf=new byte[1 << 21];
        private int bufLen,bufOffset,next;

        public FastInput(InputStream is)
        {
            this.is=is;
        }

        private int read()
        {
            while(bufLen==bufOffset)
            {
                bufOffset=0;
                try {bufLen=is.read(buf);}
                catch(IOException e){bufLen = -1;}

                if(bufLen==-1) return -1;
            }
            return buf[bufOffset++];
        }

        public void skipBlank()
        {
            while(next>=0 && next<=32) next=read();
        }

        public String next()
        {
            return readString();
        }

        public int readInt()
        {
            int sign=1;
            skipBlank();
            if(next=='+' || next=='-')
            {
                sign= next=='+'?1:-1;
                next=read();
            }
            int val=0;
            if(sign==1)
            {
                while(next>='0' && next<='9')
                {
                    val=val*10+next-'0';
                    next=read();
                }
            }
            else
            {
                while(next>='0' && next<='9')
                {
                    val=val*10-next+'0';
                    next=read();
                }
            }

            return val;
        }

        public String readString(StringBuilder builder)
        {
            skipBlank();
            while(next>32)
            {
                builder.append((char)next);
                next=read();
            }
            return builder.toString();
        }

        public String readString()
        {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }
    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable
    {
        private static final int THRESHOLD=32<<10;
        private final Writer os;
        private StringBuilder cache=new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq)
        {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite()
        {
            if(cache.length()<THRESHOLD) return;
            flush();
        }

        public FastOutput(Writer os)
        {
            this.os=os;
        }

        public FastOutput(OutputStream os)
        {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c)
        {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c)
        {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c)
        {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c)
        {
            return append(c).println();
        }

        public FastOutput println()
        {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try
            {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            }
            catch(IOException e) {throw new UncheckedIOException(e);}
            return this;
        }

        public void close()
        {
            flush();
            try {os.close();}
            catch(IOException e) {throw new UncheckedIOException(e);}
        }

        public String toString()
        {
            return cache.toString();
        }
    }
}