#include<bits/stdc++.h> using namespace std; int T; long long n,cnt,flag; long long phi(long long x){ long long ans=x; for(int i=2;i*i<=x;i++){ if(x%i==0){ ans=ans/i*(i-1); //cout<<'*'<<ans<<endl; while (x%i==0) x/=i; } } //cout<<"&"<<ans<<endl; if(x>1) ans=ans/x*(x-1); return ans; } long long qm(long long a,long long b,long long mod){ long long ans=0; while (b) { if(b&1) ans=(ans+a)%mod; b>>=1; a=(a+a)%mod; } return ans; } long long qp(long long a,long long b,long long mod){ long long ans=1; while (b) { if(b&1) ans=(qm(ans,a,mod))%mod; b>>=1; a=(qm(a,a,mod))%mod; } return ans; } int main(){ //freopen("card.in","r",stdin); //freopen("card.out","w",stdout); cin>>T; while (T--) { cin>>n; if(n==1){ cout<<1<<endl; continue; } n=2*n-1; //cout<<n; long long tmp=phi(n); //cout<<'!'<<tmp<<endl; long long ans=0x3f3f3f3f3f3f3f3f; for(long long i=1;i*i<=tmp;i++){ if(tmp%i==0){ //cout<<i<<' '<<qp(2,i,2*n-1)<<endl; if(qp(2,i,n)==1){ ans=min(ans,i); } if(qp(2,tmp/i,n)==1){ ans=min(ans,tmp/i); } } } cout<<ans<<endl; } return 0; }