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


/*
   AUTHOR 
    
    Mr. PANKAJ GOYAL 
    Coding Lover 
                     */
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef unordered_map<int,int> umii;
typedef unordered_map<ll, ll> umll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;

#define      unsigned long long int ull
#define      fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define      F first
#define      S second
#define      f(i,n) for (int i = 0; i < n; i++)
#define      fr(i,n) for(int i=(int)n-1;i>=0;--i)
#define      fo(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define      pb push_back
#define      mp make_pair
#define      pri_que_down priority_queue<ll>
#define      pri_que_up  priority_queue<ll, vector<ll>, greater<ll> >
#define      fix(x) fixed<<setprecision(x)


#define      display(v) for(int i =0;i<(int)v.size();++i)cout << v[i] << " "
#define      all(v) v.begin(),v.end()
#define      rall(v) v.rbegin(),v.rend()
#define      read(a) for(int i = 0;i<(int)a.size();++i)cin>>a[i]
#define       inf  4e18;


const int mod = 1e9 + 7;
const double PI = 3.1415926535897932384626;

const int nax = 300*1000 + 10;
int fac[nax];
int mod_inv[nax];


inline int add(int a, int b){ int c = (a%mod) + (b%mod); if(c >= mod) c -= mod; return c; }
inline int mul(int a, int b){ return ((a%mod) * 1ll * (b%mod)) % mod; }
inline int sub(int a, int b){ int c = (a%mod) - (b%mod); if(c < 0) c += mod; return c; }
inline ll gcd(ll a,ll b){return __gcd(a,b);}
inline ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
inline string ans(bool a) { if(a) return "YES\n"; else return "NO\n";}
// ---------------------------------------*******************--------------------------------------//

ll power(ll x,ll y) 
{ 
    ll p=mod;
    ll res = 1;
    x=x%p;  
    while(y>0) 
    { 
        if (y&1) res=(res*x)%p;
        y=y>>1; 
        x=(x*x)%p; 
    } 
    return res; 
} 
void pre(){
    fac[0] = fac[1] = 1;
    for(int i = 2;i<nax;++i){
        fac[i] = mul(i , fac[i-1]);
    } 
    mod_inv[0] = mod_inv[1] = 1;
    for(int i =2;i<nax;++i){
        mod_inv[i] = power(fac[i] , mod - 2);
    }
 
}
ll ncr(ll n, ll r)
{
    if(r > n)return 0LL;
    int ans = mul(fac[n] , mod_inv[r]);
    ans = mul(ans , mod_inv[n-r]);
    return ans;
}

ll str_to_int(string s)
{
    stringstream geek(s); 
    ll x=0; 
    geek>>x; 
    return x;
}
string int_to_str(ll n)
{
    return to_string(n);
}


ll HCF_of_vl(vl &A)
{
    ll i,a,n=A.size();
    a=A[0];
     fo(i,1,n)
    a=__gcd(a,A[i]);
    return a;
}

ll LCM_of_vl(vl &A)
{
    ll i,a,b,n=A.size();
    a=A[0];b=A[0];
    fo(i,1,n)
    {
       b=__gcd(a,A[i]);
       a=(a*A[i])/b;
     }
     return a;
}


map<ll,ll> count_freq_vl(vl &A)
{
    map<ll,ll>result;
    ll i,n=A.size();
    f(i,n)
    result[A[i]]++;
    return result;
}


void factorize(ll n) 
{ 
	ll i,count = 0; 
	while (!(n % 2)) { 
		n >>= 1; 
		count++; 
	} 
	if (count)  cout<<"2 : "<<count<<"\n";
	for (i=3; i<=sqrt(n);i+= 2) { 
		count=0; 
		while(n%i == 0){ 
			count++; 
			n=n/i; 
		} 
		if (count) 
		cout<<i<<" : "<<count<<"\n";
	} 
	if (n>2) 
	cout<<n<<" : 1"<<"\n";
} 
void Prime(ll n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));
    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
    for (int p=2; p<=n; p++)
       if (prime[p])
          cout << p << " ";
}
vl count_bits_vl(vl &v)
{
    ll i,j;
     vl counts(31,0);
    for(i=0;i<31;i++)
    {
        for(j=0;j<v.size();j++) if((1ll<<i)&v[j]) counts[i]++;
    }
    return counts;
}
vl make_fact_vl(ll n)
{
     vl fact; fact.pb(1);
    for(ll i=1;i<=n;i++) fact.pb((i*fact[i-1])%mod);
    return fact;
}
void fib(ll n)
{
    vl f;
    f.pb(1);f.pb(1);f.pb(2);
    for(ll i=3; i<n; i++)
     f.pb((f[i-1]%mod+f[i-2]%mod)%mod);
}
ll mod_inverse(ll n)
{
    return power(n,mod-2);
}
 
/* ---------------------------------------*******************--------------------------------------
                                ll power(ll a,ll b)ll fact(ll n)    
                                ll ncr(ll fact[],ll n, ll r)
                                ll str_to_int(string s)
                                string int_to_str(ll n)
                                ll HCF_of_vl(vl &A)
                                ll LCM_of_vl(vl &A)
                                map<ll,ll> count_freq_vl(vl &A)
                                void factorize(ll n)
                                void Prime(int n)
                                vl count_bits_vl(vl &v)
                                vl make_fact_vl(ll n)
                                void fib(ll n)
                                ll mod_inverse(ull n, ull p)
 *****----------------------------------*******************--------------------------------------*/

const ll N = 10000000 + 5;
vl A(N,1),B(N,-1);

void pankaj(){
    ll i,j;
    for(i =2;i<N; ++i){
        for(j = i ; j<N; j+= i) A[j] += i;
        B[i] = INT_MAX;
    }
    for(i=1;i<N; i++)
    {
     if(A[i] < N && B[A[i]]==-1 )
         B[A[i]]=i;
    }
}

 

   
 
// ---------------------------------------*******************--------------------------------------//

void solve()
{
     ll t=1;
     cin>>t;
      while(t--)
      {
         ll x; cin>>x;
         cout<<B[x]<<"\n";
      }
}

signed main()
{
     fast;
   pankaj();
  //  pre();
    solve();

    return 0;
}












