#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ull unsigned long long
#define i128 __int128
#define int long long
using namespace std;
inline i128 read()
{
	char c=getchar();i128 x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

mt19937_64 rnd(114514);

// lazy to write these
__int128 mul(__int128 a,__int128 b,__int128 p)
{
	__int128 mul=a,res=0;
	while (b)
	{
		if (b&1) res=(res+mul)%p;
		mul=(mul+mul)%p,b>>=1;
	}
	return res;
}
__int128 qpow(__int128 a,__int128 b,__int128 p)
{
	__int128 mul=a,res=1;
	while (b)
	{
		if (b&1) res=::mul(res,mul,p);
		mul=::mul(mul,mul,p),b>>=1;
	}
	return res;
}
__int128 gcd(__int128 x,__int128 y)
{
	if (y==0) return x;
	return gcd(y,x%y);
}
__int128 get_pow(__int128 a,int b,__int128 c)
{
	__int128 mul=1;
	bool op=0;
	for (int i=1;i<=b;++i)
	{
		if (mul<=c/a) mul*=a;
		else op=1;
	}
	return op?c+1:mul;
}
i128 pw[999];
bool isp(__int128 x)
{
	if (x%2==0||x%3==0||x%5==0||x%7==0||x%11==0) return 0;
	__int128 a,d=x-1;
	int res=0;
	while (!(d&1)) d>>=1,res++;
	for (int i=1;i<=10;++i)
	{
		a=rnd()%1000000000+1,pw[0]=qpow(a,d,x);
		for (int j=1;j<=res;++j) pw[j]=mul(pw[j-1],pw[j-1],x);
		if (pw[res]!=1) return 0;
		for (int j=res-1;j>=0;--j)
		{
			if (pw[j]==x-1) break;
			if (pw[j]!=1) return 0;
		}
	}
	return 1;
}
__int128 rtd(__int128 x,__int128 d)
{
	__int128 y=0;
	for (int i=log(2e18)/log(2);i>=0;--i)
		if (y+(1ll<<i)<=2e18&&get_pow(y+(1ll<<i),d,x)<=x)
			y+=(1ll<<i);
	return y;
}

int B=45000,BB=(B+1)*(B+1);
int pri[maxn],tot;
bool vis[maxn];
void sieve(int n){
	For(i,2,n){
		if(!vis[i]) pri[++tot]=i;
		For(j,1,tot){
			int x=i*pri[j];
			if(x>n)break;
			vis[x]=1;
			if(i%pri[j]==0)break;
		}
	}
}

map<i128,int>mp;
int cnt;
i128 m,m2;
int V=1e18;
void solve(i128 x){
//	cout<<"solve "<<(int)x<<'\n';
	if(x==1)return;
	if(isp(x)){
		mp[x]=1;
		return;
	}
	For(i,2,10){
		i128 d=rtd(x,i);
		if(isp(d) && get_pow(d,i,x)==x){
			mp[d]=1;
			return;
		}
	}
	while(1){
		i128 a=rnd()%V+1;
		while(gcd(a,m)!=1) a=rnd()%V+1;
		i128 qp=qpow(a,m,x);
		if(qp!=1){
			i128 tmp=gcd(x,qp-1);
			solve(tmp);
			return;
		}
		i128 pw0=qpow(a,m2,x);
		i128 pw1=mul(pw0,pw0,x);
		int step=0;
		while(1){
			if(pw0==-1 || pw0==x-1)break;
			if(pw0!=1 && pw1==1){
				i128 tmp=gcd(pw0+1,x);
				solve(tmp);
				solve(x/tmp);
				return;
			}
			pw0=pw1;
			pw1=mul(pw0,pw0,x);
			++step;
			if(step>cnt)break;
		}
	}
}

void work()
{
	mp.clear();
	i128 x=read()*2,X=x; m=X;
	cnt=0;
	while(x%2==0)x/=2,++cnt;
	m2=x;
	x=X;
	For(i,1,tot)
		while(x%pri[i]==0)x/=pri[i],mp[pri[i]]=1;
	solve(x);
	vector<i128>o;
	for(auto it:mp) o.pb(it.fi);
//	for(auto x:o) cout<<(long long)x<<'\n';
	i128 now=X;
	long long res=1;
	Rep(i,(int)o.size()-1,0){
		int cc=0;
		while(now%o[i]==0)now/=o[i],++cc;
		if(!cc)continue;
		For(j,1,(cc+1)/2)res*=o[i];
	//	cout<<"cc "<<cc<<endl;
		now/=(o[i]-1);
	}
	cout<<res<<"\n";
}

signed main()
{
	sieve(B);
	int T=read();
	while(T--)work();
	return 0;
}
/*
3
20
21
475750381222420656586462245096576000
*/