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 : XDU_mzb
------- QQ:3157347078
------- Talk is cheap,show me the code.
-------
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
struct BST : tree<pair<ll,ll>, null_type, less<pair<ll,ll> >, rb_tree_tag, tree_order_statistics_node_update>
  {
  	unordered_map<ll,ll> count;
  	void ins(ll val)
  	  {
  	  	insert(make_pair(val, ++count[val]));
		}
	void del(ll val)
	  {
	  	if (count[val] > 0)
	  	  erase(make_pair(val,count[val]--));
	  }
	ll rak(ll val)
	  {
	  	return order_of_key(make_pair(val,1)) + 1;
	   }
	ll kth(ll val)
	  {
	  	return find_by_order(val - 1) -> first;
	  }
	ll pre(ll val)
	  {
	  	return find_by_order(order_of_key(make_pair(val, 0)) - 1) ->first;
	  }
	ll net(ll val)
	  {
	  	return upper_bound(make_pair(val, INT32_MAX)) -> first;
	  }
  };
struct BIT
  {
  	static const  ll maxsize = 1000000 * 3;
  	ll date[maxsize + 110];
  	void clear(ll n)
  	  {
  	  	fill(date + 1,date + 1 + n,0ll);
		}
  	ll lowbit(ll n)
  	  {
  	  	return n & -n;
		}
	void add(ll pos,ll val)
	  {
	  	while (pos <= maxsize)
	  	  date[pos] += val,
	  	  pos += lowbit(pos);
	  }
	ll sum(ll pos)
	  {
	  	ll ret = 0;
	  	while (pos)
	  	  ret += date[pos],
	  	  pos -= lowbit(pos);
	  	return ret;
	  }
	ll sum(ll star,ll fini)
	  {
	  	return sum(fini) - sum(star - 1);
	  }
  };
struct LS
  {
  	ll date[1000000 * 3 + 110];
  	ll cnt;
  	void clear()
  	  {
  	  	cnt = 0;
		}
	void ins(ll val)
	  {
	  	date[cnt++] = val;
	  }
	void build()
	  {
	  	sort(date,date + cnt);
	  	cnt = unique(date,date + cnt) - date;
	  }
	ll ls(ll val)
	  {
	  	return lower_bound(date,date + cnt,val) - date + 1;
	  }
	ll re(ll val)
	  {
	  	return date[val - 1];
	  }
  };
#define debug(x) cerr << "debug+ " #x " = " << x << endl
const ll mod = 998244353;
ll qp(ll a,ll b = mod - 2,ll mod = mod)
  {
  	ll ret = 1;
  	a %= mod;
  	while (b)
  	  {
  	  	if (b & 1)
  	  	  ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
		}
	return ret;
  }
ll r()
  {
  	ll c,f = 1,x = 0;
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-0x30;
    return f*x;
  }
void w(ll x)
  {
  	if(x < 0)
	  {
        putchar('-');
        x = -x;
      }
    if (x > 9)
      w(x / 10);
    putchar(x % 10 + '0');
	}
bool isp(ll n)
  {
  	if (n <= 2 or n % 2 == 0)
  	  return n == 2;
  	for (ll i = 3;i * i <= n;i += 2)
  	  if (n % i == 0)
  	    return 0;
  	return 1;
  }
template<typename T1,typename T2>
ostream& operator << (ostream& os,pair<T1,T2> rhs)
  {
  	return os << "(" << rhs.first << "," << rhs.second << ")";
   }
template<typename T>
void show(T con,string info = "")
  {
  	cout << info << " ";
  	for (auto it : con)
  	  cout << it << " ";
	cout << endl;
  }
ll d(ll n)
  {
  	ll ret = 0;
  	for (ll i = 1;i <= n;i++)
  	  if (n % i == 0)
  	    ret += i;
  	return ret;
  }
ll s(ll p,ll m)
  {
  	ll ret = 0;
  	ret = (qp(p,m + 1) - 1) / (p - 1);
  	return ret;
  }
vector<ll> p;
ll dfs(ll n,ll pos)
  {
  	if (n == 1)
  	  return 1;
  	ll ret = 1e10;
  	if (pos == -1)
  	  return ret;
  	for (ll i = 1;s(p[pos],i) <= n;i++)
  	  if (n % s(p[pos],i) == 0)
		{
			ret = min(ret,qp(p[pos],i) * dfs(n / s(p[pos],i),pos - 1));
		}
	return min(ret,dfs(n,pos - 1));
  }
ll f[10000000 + 110];
void pre(ll n = 1e7)
  {
  	static bool vis[10000000 + 110];
  	f[1] = 1;
  	static ll pri[5000000 + 110];
  	ll cnt = 0;
  	for (ll i = 2;i <= n;i++)
  	  {
  	  	if (vis[i] == 0)
  	  	  {
  	  	  	pri[cnt++] = i;
  	  	  	f[i] = i + 1;
			  }
		for (ll k = 0;k < cnt and pri[k] * i <= n;k++)
		  {
		  	vis[i * pri[k]] = 1;
		  	ll a = i;
		  	ll b = pri[k];
		  	ll mi = 1;
		  	while (a % pri[k] == 0)
		  	  a /= pri[k],
		  	  b *= pri[k],
			  mi++;
		  	if (a != 1)
		  	  f[i * pri[k]] = f[a] * f[b]; 
		  	else
		  	  f[i * pri[k]] = s(pri[k],mi);
			if (i % pri[k] == 0)
		  	  break;
		  }
		}
  }
ll ans[10000000 + 110];
int main()
  {
  	pre();
  	for (ll i = 1;i <= 1e7;i++)
  	  if(f[i] <= 1e7){
  	  	if (ans[f[i]] == 0)
  	    ans[f[i]] = i;
  	  else
  	    ans[f[i]] = min(ans[f[i]],i);
		}
  	  
	//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll T = 1;
	cin >> T;
	for (ll ttt = 1;ttt <= T;ttt++)
	  {
	  	ll n;
	  	cin >> n;
	  	cout << (ans[n] == 0 ? -1 : ans[n]) << "\n";
	   }
	return 0;
  }

