#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e7+10; int T,n,ans; int b[N],pre[N]; signed main(){ // freopen("card.in","r",stdin); // freopen("card.out","w",stdout); scanf("%lld",&T); while(T--){ scanf("%lld",&n); b[0]=1;pre[0]=1; for(int i=1;i<=n*2+1;i++){ b[i]=(b[i-1]*2)%(2*n-1); pre[i]=(pre[i-1]+b[i])%(2*n-1); if(pre[i]==0){ ans=i+1;break; } } printf("%lld\n",ans); } // fclose(stdin); // fclose(stdout); return 0; }