#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e7+10; int T,n,p[N],cnt; int phi(int m){ // cout<<m<<endl; int res=m; for(int i=2;i*i<=m;i++){ if(m%i)continue; while(m%i==0){m/=i;} res=res/i*(i-1); // cout<<i<<" "<<res<<" "<<m<<endl; } if(m!=1)res=res/m*(m-1); return res; } int ksm(int a,int b,int m){ int ans=1,base=a; while(b>0){ if(b&1){ans=(__int128_t)ans*base%m;} base=(__int128_t)base*base%m; b>>=1; } return ans; } bool check(int i){return ksm(2,i,n*2-1)==1;} signed main(){ // freopen("card.out","w",stdout); cin>>T; while(T--){ cnt=0; cin>>n; if(n==1){cout<<1<<endl;continue;} // cout<<n<<endl; int k=phi(2*n-1); // cout<<k<<endl; for(int i=1;i*i<=k;i++){ if(k%i==0){p[++cnt]=i;} } for(int i=cnt;i>=1;i--){p[cnt*2-i+1]=k/p[i];} for(int i=1;i<=cnt*2;i++){ if(check(p[i])){ cout<<p[i]<<endl; break; } } } return 0; }