#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<random>
#include<map>
#include<cassert>
#define N 1000000
#define inf 1e9
#define INF 2e18
using namespace std;
mt19937 RAND(0);
__int128 read()
{
	char c=0;
	__int128 sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct node
{
	__int128 num,data;
};
node tong[N+1];
int T,length,maxn=1000000000,cnt,v[N+1],st[N+1],leng;
bool nprime[N+1];
__int128 n,m,sm,pw[N+1],maxinf=(__int128)(1e36);
map<__int128,int>p;
void write(__int128 x)
{
	if (!x) return;
	write(x/10),printf("%d",(int)(x%10));
	return;
}
__int128 fast_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 fast_pow(__int128 a,__int128 b,__int128 p)
{
	__int128 mul=a,res=1;
	while (b)
	{
		if (b&1) res=fast_mul(res,mul,p);
		mul=fast_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;
}
__int128 F(__int128 x,__int128 d)
{
	__int128 y=0;
	for (int i=log(INF)/log(2);i>=0;--i)
		if (y+(1ll<<i)<=INF&&get_pow(y+(1ll<<i),d,x)<=x)
			y+=(1ll<<i);
	return y;
}
bool isprime(__int128 x)
{
	if (x<=N) return (!nprime[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=RAND()%maxn+1,pw[0]=fast_pow(a,d,x);
		for (int j=1;j<=res;++j) pw[j]=fast_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;
}
void solve(__int128 x)
{
	if (x<=N)
	{
		while (x!=1) p[v[x]]++,x/=v[x];
		return;
	}
	__int128 a,d;
	for (int i=1;st[i]<=10000;++i)
		if (x%st[i]==0)
		{
			p[st[i]]++,solve(x/st[i]);
			return;
		}
	for (int i=1;i<=10;++i)
	{
	    d=F(x,i);
		if (isprime(d)&&get_pow(d,i,x)==x)
		{
			while (x%d==0) x/=d,p[d]++;
			return;
		}
	}
	for (int i=1;i<=10;++i)
	{
		a=RAND()%maxn+1;
		while (gcd(a,m)!=1) a=RAND()%maxn+1;
		if (fast_pow(a,m,x)!=1)
		{
			d=gcd(x,(fast_pow(a,m,x)-1)%x);
			solve(d),solve(x/d);
			return;
		}
		else
		{
			pw[0]=fast_pow(a,sm,x);
			for (int i=1;i<=cnt;++i) pw[i]=fast_mul(pw[i-1],pw[i-1],x);
			for (int i=cnt-1;i>=0;--i)
			{
				if (pw[i]==-1) break;
				if (pw[i]!=1)
				{
					d=gcd(pw[i]+1,x),solve(d),solve(x/d);
					return;
				}
			}
		}
	}
	return;
}
int main()
{
	__int128 x;
	for (int i=2;i<=N;++i)
		if (!nprime[i])
		{
			st[++leng]=v[i]=i;
			for (int j=(i<<1);j<=N;j+=i) v[j]=i,nprime[j]=1;
		}
	T=read();
	while (T--)
	{
		sm=m=read()<<1,length=cnt=0,n=1,p.clear();
		while (!(sm&1)) sm>>=1,cnt++;
		solve(m);
		for (auto it:p) tong[++length]=(node){it.first,it.second};
		for (int i=length;i>=1;--i)
			if (tong[i].data)
			{
				for (int j=1;j<=((tong[i].data+1)>>1);++j) n*=tong[i].num;
				x=tong[i].num-1;
				for (int j=1;j<=i-1;++j)
					while (x%tong[j].num==0)
						x/=tong[j].num,tong[j].data--;
			}
		write(n),puts("");
	}
	return 0;
}