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 CPP):

Solution:
#include<bits/stdc++.h>
//#define int long long
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
using namespace std; 
//using namespace __gnu_pbds; 
#define pii pair<int,int>
#define float double
#define pb push_back 
#define lp(i,j,n) for( i=j;i<n;i++) 
#define lop(j,k,n)for( j=k;j<n;j++)
#define m_p make_pair
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define minheap priority_queue<int,vector<int>,greater<int>>
#define maxheap priority_queue<int>
#define kickstart  cout<<"Case #"<<tt<<": "
#define pair_pq priority_queue<pii,vector<pii> ,greater<pii>>
#define ff first
#define ss second
#define pff pair<float,float>
typedef long long ll;
typedef long double ld ;
#define pll pair<ll , ll>
#define piii pair<int,pii>
#define all(x)x.begin(),x.end()
#define vi vector<int> 



// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>



#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
    for ( \
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second; \
        debug("%s: %d ms\n", d, (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
    )



int dx[4] = { 1 , -1 , 0 , 0 };
int dy[4] = { 0 , 0  , 1 , -1};

void show(vector<ll> a){for(auto x :a )cout<<x <<" ";}
const ll  M =2e3 + 5,mod = 998244353 ,MOD = 1e9 + 7 , inf =1e18 , MAX = 2e5 + 5  ;

string alph = "abcdefghijklmnopqrstuvwxyz";

map<ll,ll>mp;
const int N = 10000000 +10;
int lp[N+1];
ll dp[N +1];
vector<int> pr , ans(N , -1);
void linear_SIEVE(){
for (int i=2; i<=N; ++i) {
    if (lp[i] == 0) {
        lp[i] = i;
        pr.push_back (i);
    }
    for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
        lp[i * pr[j]] = pr[j];
}
}

void precompute()
 {
    dp[1] = 1;
    for(ll i = 2 ; i < N ; i++)
       {
          if(lp[i] == i)
             {
               dp[i] = i + 1;
              // if(!mp[dp[i]])mp[dp[i]] = i;
               continue;
             }

             int j =  i ; 
             dp[i] = 1;
             while(j%lp[i] == 0)
               {
                 dp[i] = dp[i]*lp[i] + 1 ;
                 j/=lp[i];
               }
               dp[i]*=dp[j]; 
               //if(!mp[dp[i]])mp[dp[i]] = i;
       }
 }


void solve(int tt ){
ll  i , j , n  , m  ;
int l , r , s  ; 
cin >> n ;

cout << ans[n] <<"\n";

}
signed main() 
{
 
 fastio
    ll i  ;
    ll T = 1 ;
   //
    //
    linear_SIEVE();
    precompute();
   for(int i = N - 1; i >= 1 ; i--)
      if(dp[i] < N)
         {
           ans[dp[i]] = i;
         }

    cin >> T ;

    time__("Exec Time : "){

      ll x = 1 ; 
      while( x <= T ){
        solve(x);
        x++;
      }
    }

  return 0;
 }

/*
 1 --> DO NOT STAY STUCK ON ONE APPROACH

 2 --> DO NOT SIT IDLE . DO SMTHING

 3 --> STAY ORGANISED .










vector<bool>taken(n+1 , false);
  for(int j = l ; j <= r ; j--)
          taken[a[j]] = true;
  vi avail ;
  lp( j , 1, n + 1)if(!taken[j])avail.pb(j);
  lp( j , 1 , n + 1){  if(a[j] == 0){ a[j] = avail.back() ; avail.pop_back();} cout << a[i] <<" ";}

  cout <<endl;


*/