#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!=0)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(ck(2,i,2*x+1)==1){ ans=i; break; } else if(ck(2,t/i,2*x+1)==1){ ans=min(ans,t/i); } } printf("%lld\n",ans); } return 0; }