#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll __int128
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int 
using namespace std;
const int N = 1 << 20;

int ctz(ll x) {
	if(!x) return 128;
	int cnt = 0;
	while(!(x & 1)) ++cnt, x >>= 1;
	return cnt;
}
ll gcd(ll a, ll b) {
	if(!a || !b) return a + b;
    ll az = ctz(a);
    ll bz = ctz(b);
    ll z = min(az, bz);
    b >>= bz;
    while(a) {
        a >>= az;
        ll diff = a - b;
        az = ctz(diff);
        b = min(a, b), a = diff > 0 ? diff : -diff;
    }
    return b << z;
}
mt19937_64 orz;

const int test[12] = {2, 3, 5, 7, 11, 13, 17, 19, 233}, K = 8;
ll x;
inline ll Mul(ll a, ll b, ll mod) {
	ll o = a * b - (ll) ((__float128) a * b / mod) * mod;
	while(o < 0) o += mod;
	while(o >= mod) o -= mod;
	return o; 
}
inline ll qpow(ll x, ll y, ll mod) {
	ll ret = 1;
	for(; y; x = Mul(x, x, mod), y >>= 1) if(y & 1) ret = Mul(ret, x, mod);
	return ret;
}
bool MR (ll x) {
	if(x <= test[K]) {
		L(i, 2, sqrt((int)x)) 
			if(x % i == 0) 
				return false;
		return true;
	}
	int j, k = 0;
	ll a = x - 1;
	for(; !(a & 1); a >>= 1, ++k) ;
	L(i, 0, K) {
		ll w = qpow(test[i], a, x); 
		if(w == 1 || w == x - 1) continue ;
		for(j = 0; j < k; ++j) {
			w = Mul(w, w, x);
			if(w == x - 1) break ;
		}
		if(j == k) return false;
	}
	return true;
}

template < typename T > inline void read(T &r) {
	r = 0; bool w = 0; char ch = getchar();
	while(ch < '0' || ch > '9') w = ch == '-', ch = getchar();
	while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
	r = w ? - r : r;
}
void print(ll x) {
	if(x > 9) print(x / 10);
	cout << ((int) (x % 10));
}
ll POW(ll x, int k) {
	ll ret = 1;
	for(; k; x = x * x, k >>= 1) if(k & 1) ret = ret * x;
	return ret;
}
void Main() {
//	x = (ll) 30011 * 30011 * 30011 * 30010;
	read(x);
	
//	ll Z = orz() % (T / 10000);
//	x = Z * (Z - 1) / 2;
//	while(x <= 1e18) x *= 2;
	if(x == 1) {
		cout << 1 << '\n';
		return ;
	}
	x *= 2;
	ll nx = x;
	int cnt = 0;
	while(nx % 2 == 0) nx /= 2, ++cnt;
	vector < ll > V, dc;
	L(tst, 0, 30) {
		ll rnd = orz() % x;
		ll z = qpow(rnd, nx, x);
		L(o, 0, cnt) {
			if(!z) break;
			ll k = gcd(z - 1, x);
			if(1 < k && k < x) dc.emplace_back(k); 
			if(o) z = Mul(z, z, x);
		}
	}
	sort(dc.begin(), dc.end());
	dc.erase(unique(dc.begin(), dc.end()), dc.end());
	V.emplace_back(x); 
	for(auto u : dc) {
		L(i, 0, sz(V) - 1) {
			ll G = __gcd(V[i], u);
			if(1 < G && G < V[i]) {
				V.emplace_back(V[i] / G), V[i] = G;
			}
		}
	}
	dc.clear();
	for(auto &z : V) {
		ll mxd = 0, Pw = 0;
		L(pw, 1, 120) {
			if(((ll)1 << pw) > z) break;
			ll o = floor(pow(z, (long double)1 / pw));
			L(t, 0, 3) {
			if(o > 1 && fabs(pow((long double)o, pw) - z) < 100 && POW(o, pw) == z) 
				mxd = o, Pw = pw;
			++t;
			}
		}
		L(i, 1, Pw) 
			dc.emplace_back(mxd);
	}
	swap(dc, V);
	sort(V.begin(), V.end());
	reverse(V.begin(), V.end());
//	for(auto &t : V) {
//		cout << t << ' ';
//	}
//	cout << endl;
	
	ll cx = x;
	ll ans = 1;
	for(auto z : V) {
		if((cx % z == 0) && MR(z)) {
			int cnt = 0;
			while(cx % z == 0) cx /= z, ++cnt;
			if((cx % (z - 1)) || !(cnt & 1)) {
				cout << -1 << '\n';
				return ;
			}
			cx /= z - 1;
			L(i, 1, (cnt + 1) / 2) ans *= z;
		}
	}
	if(cx != 1) {
		cout << -1 << '\n';
		return ;
	}
	print(ans), cout << '\n';
}
int main () {
	int t; read(t); while(t--) Main();
	return 0;
}
/*
20
21
475750381222420656586462245096576000
*/