#include<iostream> #include<ctime> using namespace std; #define timeMS (clock()*1000/CLOCKS_PER_SEC); #define int long long using bigint=__int128_t; inline int fpow(int a,int b,int P){ int c=1; for(;b;b>>=1,a=((bigint)a*a%P))if(b&1)c=((bigint)c*a%P); return c; } inline int phi(int x){ int res=1; for(int i=2;i*i<=x;i++)if(x%i==0){ res*=i-1; x/=i; while(x%i==0)res*=i,x/=i; } if(x>1)res*=x-1; return res; } signed main(){ // freopen("card.in","r",stdin); // freopen("card.out","w",stdout); int T;cin>>T; while(T--){ int n;cin>>n;n*=2; if(n==2){cout<<"1\n";continue;} int x=phi(n-1); int now=0; int res=0; for(int i=1;i*i<=x;i++)if(x%i==0){ now=i; if(fpow(2,i,n-1)==1){res=i;break;} } if(res){cout<<res<<endl;continue;} for(int i=now;i>=1;i--)if(x%i==0){ if(fpow(2,x/i,n-1)==1){res=x/i;break;} } cout<<res<<endl; } // cerr<<timeMS; return 0; }