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>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;
#define int             long long
#define pb              push_back
#define mod             1000000007
#define nl              "\n"
#define vi              vector<int>
#define F               first
#define S               second
#define fr(i,n)         for (int i = 0; i < n; ++i)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x)          x.begin(),x.end()
#define pbds            tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
int power(int a, int b, int m) {int ans = 1; while (b) {if (b & 1) ans = (ans * a) % m; b /= 2; a = (a * a) % m;} return ans;}
int power(int a, int b) {int ans = 1; while (b) {if (b & 1) ans = (ans * a); b /= 2; a = (a * a);} return ans;}
int modinv(int a, int m)  {return power(a, m - 2, m);}
void start()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
///////////////////////////////////////////////////////////////////
const int N = 200005;

vi arr(N,1);
map<int,int>mp;
vector<bool> is_prime(1e7, true);
void prime(){
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= 1e7; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= 1e7; j += i)
                is_prime[j] = false;
        }
    }
}


void init(){
    for(int i=2;i<N;i++){
        for(int j=i;j<N;j+=i){
            arr[j]+=i;
        }
    }
    mp[1]=1;
    for(int i=2;i<N;i++){
        if(arr[i]==1 or mp.find(arr[i])!=mp.end()) continue;
        mp[arr[i]]=i;
    }
    
}
void solution()
{
    int c;cin>>c;
    if(c>N and is_prime[c-1]){
        cout<<c<<nl;return;
    }
    if(mp.find(c)==mp.end()) cout<<-1;
    else cout<<mp[c];
    cout<<nl;
}


////////////////////////////////////////////////////////////////////
int32_t main()
{
    FIO;
    start();
    int t = 1;
    cin >> t;
    init();
    prime();
    fr(i,t) {
        // cout << "Case #" << i+1 << ": ";
        solution();
    }
    // #ifndef ONLINE_JUDGE
    //     cerr << "\nTime Taken : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
    // #endif
}