#include <bits/stdc++.h> using namespace std; using Int = long long; const char newl = '\n'; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);} template<typename T=Int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } vector<Int> identity(Int n){ vector<Int> ord(n); iota(ord.begin(),ord.end(),0); return ord; } template<typename T> T mod_pow(T a,long long n,T mod){ using ll = long long; T res(1); while(n){ if(n&1) res=(ll)res*a%mod; a=(ll)a*a%mod; n>>=1; } return res; } // min m s.t. a^m = 1 mod n (a, n are coprime) template<typename T> T carmichael_lambda(T n){ auto lcm=[](auto a,auto b){return a/__gcd(a,b)*b;}; T res=1; if(n%8==0) n/=2; for(int i=2;i*i<=n;i++){ if(n%i==0){ T tmp=i-1; for(n/=i;n%i==0;n/=i) tmp*=i; res=lcm(res,tmp); } } if(n!=1) res=lcm(res,n-1); return res; } template<typename T> T order(T x,T MOD){ T res=carmichael_lambda(MOD); vector<T> cand; for(T i=1;i*i<=res;i++){ if(res%i) continue; cand.emplace_back(i); cand.emplace_back(res/i); } sort(cand.begin(),cand.end()); for(T c:cand) if(mod_pow(x,c,MOD)==1) return c; return res; } //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); auto solve=[](Int n){ return order<Int>(2,2*n-1); /* Int res=0,tmp=1; do{ tmp+=2*n-1; while(tmp%2==0) tmp/=2,res++; }while(tmp!=1); return res; */ }; auto naive=[&](Int n){ vector<Int> as=identity(2*n); Int cnt=0; do{ cnt++; vector<Int> bs(as); for(Int i=0;i<n;i++){ as[i*2+0]=bs[0+i]; as[i*2+1]=bs[n+i]; } }while(as!=identity(2*n)); return cnt; }; const Int EXPERIMENT = 0; if(EXPERIMENT){ for(Int n=1;n<=30;n++){ cout<<n<<':'<<naive(n)<<':'<<solve(n)<<newl; assert(naive(n)==solve(n)); } } Int T; cin>>T; while(T--){ Int n; cin>>n; cout<<solve(n)<<newl; } return 0; }