#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair typedef long long ll; using namespace std; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int f(int n){ vector<int>A(2*n+1); up(i,1,2*n)A[i]=i; int ct=0; while(1){ bool tg=0; up(i,1,2*n)if(A[i]!=i)tg=1; if((!tg)&&ct)break; vector<int>B(2*n+1); up(i,1,2*n){ if(i<=n)B[2*i-1]=A[i]; else B[2*(i-n)]=A[i]; }up(i,1,2*n)A[i]=B[i]; ct++; }return ct; } ll Phi(ll n){ ll res=n; for(ll i=2;i*i<=n;++i){ if(n%i)continue; while(!(n%i))n/=i; res=res/i*(i-1); }if(n!=1)res=res/n*(n-1); return res; } ll T[100]; ll mul(ll a,ll b,ll p){ ll res=0; while(b){ if(b&1)(res+=a)%=p; (a+=a)%=p;b>>=1; }return res; } ll qp(ll a,ll b,ll p){ ll res=1; while(b){ if(b&1)res=mul(res,a,p); a=mul(a,a,p);b>>=1; }return res; } ll g(ll n){ if(n==1)return 1; n=n*2-1; ll phi=Phi(n); //assert(qp(2,phi,n)==1); ll k=phi;int cc=0; for(ll i=2;i*i<=k;++i){ if(k%i)continue; while(!(k%i))T[++cc]=i,k/=i; }if(k!=1)T[++cc]=k; ll nw=phi; up(i,1,cc)if(qp(2,nw/T[i],n)==1)nw/=T[i]; return nw; //int val=1,ct=0; //while(1){ // if(val==1&&ct)break; // val=val*2%n,ct++; //}return ct; } void slv(){ ll n=read(); printf("%lld\n",g(n)); } int main(){ //freopen("card.in","r",stdin); //freopen("card.out","w",stdout); //up(i,1,1000)assert(f(i)==g(i)); int t=read();while(t--)slv(); fclose(stdin); fclose(stdout); return 0; }