#include<bits/stdc++.h> using namespace std; const int N = 150,M = 300; #define int long long int T,n,a[N],b[M]; __int128_t qpow(__int128_t x,__int128_t y,__int128_t md){ __int128_t tmp=1; while(y){ if(y&1) tmp=tmp%md*x%md; x=x%md*x%md; y=(y>>1); } return tmp; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>T; while(T--){ cin>>n; if(n==1){ cout<<1<<endl; continue; } int x=n*2-1,y,cnt=0,tot=0; y=sqrt(x); for(int i=2;i<=y;i++){ if(x%i==0){ int p=i; for(int j=1;j<=cnt;j++){ while(p%a[j]==0){ p=p/a[j]; } } if(p>1){ a[++cnt]=p; } b[++tot]=i; } } for(int i=tot;i>=1;i--){ int p=x/b[i]; for(int j=1;j<=cnt;j++){ while(p%a[j]==0){ p=p/a[j]; } } if(p>1){ a[++cnt]=p; } } int g=x; for(int j=1;j<=cnt;j++){ while(g%a[j]==0){ g=g/a[j]; } } if(g>1){ a[++cnt]=g; } int z=x; for(int i=1;i<=cnt;i++){ z=z-z/a[i]; } int q=sqrt(z),ans=5e18; for(int i=1;i<=q;i++){ if(z%i==0){ if(qpow((__int128_t)2,(__int128_t)i,(__int128_t)x)==1){ ans=min(ans,i); } if(qpow((__int128_t)2,(__int128_t)z/i,(__int128_t)x)==1){ ans=min(ans,z/i); } } } cout<<ans<<endl; } return 0; }