ll T,N,p,q;
ll loop(){
	if(N==1)return 1;
	N=2*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(loop()); }