#include<bits/stdc++.h> #define ll long long #define i128 __int128_t using namespace std; const int N=1.5e7+10,mod=998244353; ll n,x; bool isp[N]; vector<int> p;int lim=1.5e7+5; void init(){ for(int i=2;i<=lim;i++){ if(!isp[i]) p.push_back(i); for(auto it:p){ if(i*it>lim) break; isp[i*it]=1; if(i%it==0) break; } } }ll qp(ll a,ll b,ll m){ ll x=1; while(b){ if(b&1) x=(i128)x*a%m; b>>=1;a=(i128)a*a%m; }return x; } bool chk(ll p){ if(p==1) return 0; for(ll i=2;i*i<=p;i++){ if(p%i==0) return 0; }return 1; } vector<ll> w; ll gf(ll x){ ll res=1; for(auto it:w){ if(x%it==0){ x/=it;res*=(it-1); while(x%it==0) res*=it,x/=it; } }return res; }vector<ll> d2; ll dt(ll x,ll d,ll m){ ll res=1;int tmp=1; for(auto i:d2){ if(i>d) break; if(d%i==0&&qp(x,i,m)==1) return i; }return d; }void slv(){ cin>>n;n*=2;n--;w.clear(); if(n==1){ cout<<1<<endl;return ; } vector<ll> d;ll t=n; for(auto it:p){ if(t%it==0) w.push_back(it); while(t%it==0) t/=it; }if(chk(t)) w.push_back(t); ll tmp=gf(n); for(ll i=1;i*i<=tmp;i++){ if(tmp%i==0){ d2.push_back(i); if(i*i!=tmp) d2.push_back(tmp/i); } }sort(d2.begin(),d2.end()); cout<<dt(2,tmp,n)<<endl; } int main(){ init(); int t;cin>>t;while(t--) slv(); return 0; }