#include<bits/stdc++.h> #define int long long #define i128 __int128 using namespace std; inline int Phi(int x){ int ans=x; for(int i=2;i*i<=x;i++){ if(x%i==0){ ans=ans/i*(i-1); while(x%i==0)x/=i; } } if(x>1)ans=ans/x*(x-1); return ans; } inline int qpow(int a,int b,int p){ i128 ans=1; i128 c=a; while(b){ if(b&1)ans=ans*c%p; c=c*c%p; b>>=1; } return (int)ans; } inline int Get(int x){ vector<int> D; D.clear(); int P=Phi(x); for(int i=1;i*i<=P;i++){ if(P%i==0)D.push_back(i); } int T=D.size(); for(int i=T-1;i>=0;i--){ int c=P/D[i]; if(c!=D[i])D.push_back(c); } // cout<<x<<" "<<P<<endl; // for(auto t:D)cout<<t<<" "; // cout<<endl; T=D.size(); for(int i=0;i<T;i++){ // cout<<D[i]<<" "<<qpow(2,D[i],x)<<endl; if(qpow(2,D[i],x)==1)return D[i]; } } inline void Sub1(){ int T; cin>>T; while(T--){ int n; cin>>n; cout<<Get(2*n-1)<<endl;; } } signed main(){ Sub1(); }