#include<bits/stdc++.h> using namespace std; const int N = 15,M = 30; #define int long long int T,n,a[N],b[M]; __int128 qpow(__int128 x,__int128 y,__int128 md){ __int128 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=1e18; for(int i=1;i<=q;i++){ if(z%i==0){ if(qpow((__int128)2,(__int128)i,(__int128)x)==1){ ans=min(ans,i); } if(qpow((__int128)2,(__int128)z/i,(__int128)x)==1){ ans=min(ans,z/i); } } } cout<<ans<<endl; } return 0; }