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
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#pragma region DEBUG
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef
tree<
  pair<int,int>,
  null_type,
  less<pair<int,int>>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#pragma endregion DEBUG
#define MOD 1000000007
#define MAX 500005
#define endl "\n"
vector <lli> fact(MAX,1);
vector <lli> invfact(MAX,1);
vector <lli> SPF(1e7+10,MOD);
vector <lli> p(1e7+10);
vector <int> fans(10000007,-1);
lli binpow(lli a, lli b){
    lli res = 1;
    while(b > 0){
        if(b&1){
            res = res * a;
            if(res > MOD)
                return -1;
        }
        a = a*a;
        b >>= 1;
    }
    return res;
}
int PowPrime(int &n, int p){
    int ans = 0;
    while(n%p == 0){
        n /=p;
        ans++;
    }
    return ans;
}
void solve(){
    lli c;
    cin>>c;
    cout<<fans[c]<<endl;
}
int main(){
    /* freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout); */
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for(lli i = 2; i<1e7+5; i++){
        if(!p[i]){
            for(lli j = i; j<1e7+5; j+=i){
                SPF[j] = min(SPF[j],i);
                p[j] = true;
            }
        }
    }
   /*  for(lli i = 1; i<MAX-5; i++){
        fact[i] = i*fact[i-1]%MOD;
        invfact[i] = binpow(fact[i],MOD-2);
    } */
    //debug("Baby");
    for(int i = 1; i<=1e7; i++){
        int ans = 1;
        int q = i;
        /* if(i%10000 == 0)
            cout<<i<<endl; */
        while(q > 1){
            int pr = SPF[q];
            //debug(SPF[q],q);
            lli val = PowPrime(q,pr);
            if(val == 1){
                ans = ans*(pr+1);
                continue;
            }
            if(val == 2){
                ans = ans*(pr*pr + 1 + pr); 
            }
            if(val == 3){
                ans = ans*(pr*pr*pr + pr*pr + pr + 1);
            }
            if(val <= 3)
                continue;
            lli qty = binpow(pr,PowPrime(q,pr)+1)-1;
            qty /= pr-1;
            //debug(qty);
            ans = ans*qty;
        }
        if(ans > 10000000 || ans < 0)
            continue;
        if(fans[ans] == -1)
            fans[ans] = i;
        fans[ans] = min(fans[ans],i);
    }
    lli t;
    t = 1;
    cin>>t;
    lli p = 0;
    while(t--){
        p++;
        //cout<<"Case #"<<p<<": ";
        solve();
    }
}