ll T,N,p,q;ll L(){if(N==1)return 1;N+=N-1;unordered_map<ll,ll>X(4d4);p=1;rep(i,4d4)X[p]=i,p=p*2%N,if(p==1)return i+1;p=q=1;rep(i,4d4)q=q*(N/2+1)%N;rep(i,6d4)p=p*q%N,if(X.count(p))return(i+1)*4d4+X[p];}{rd(T);REP(T)rd(N),wt(L());}