#include<bits/stdc++.h> using namespace std; long long ol(long long x){ long long ans=x; for(int i=2;i*i<=x;i++){ if(x%i==0){ ans-=ans/i; while(x%i==0)x/=i; } } if(x>1)ans-=ans/x; return ans; } __int128_t ck(long long x,long long k,long long m){ if(k==1)return x; if(k%2==0){ __int128_t t=ck(x,k/2,m); return (t*t)%m; } else{ __int128_t t=ck(x,k/2,m); return (t*t*x)%m; } } int main(){ long long T; scanf("%lld",&T); while(T--){ long long x; scanf("%lld",&x); if(x==1){ printf("1\n"); continue; } if(x==0)printf("1\n"); if(x==0)continue; long long t=ol(2*x-1),ans=t; for(long long i=2;i*i<=t;i++){ if(t%i==0 && ck(2,i,2*x-1)==1){ ans=i; break; } } if(ans!=t)printf("%lld\n",ans); else{ long long tt=sqrt(t); for(long long i=tt;i>=1;i--){ if(t%(t/i)==0 && ck(2,t/i,2*x-1)==1){ ans=t/i; break; } } printf("%lld\n",ans); } } return 0; }