RT CODE:

#include<bits/stdc++.h>
using namespace std;
int t,p,ret,a,i,ph;
int POW(int b,int mod){
	ret=1,a=2;
	while (b){
		if (b&1) ret=(ret%mod*a%mod)%mod;
		a=(a%mod*a%mod)%mod;
		b>>=1;
	}
	return ret;
}
int phi(int op){
	ret=op;
	for (i=2;i<=sqrt(op);i++){
		if (op%i==0){
			while (op%i==0) op/=i;
			ret=ret*(i-1)/i;
		}
	}
	if (op>1) ret=ret*(op-1)/op;
	return ret;
}
int solve(int m){
	if (m==1||m==0) return 0;
	int ph=phi(m);
	return POW(solve(ph)+ph,m);
}
int main(){
	cin>>t;
	while (t--){
		scanf("%d",&p);
		printf("%d\n",solve(p));
	}
	return 0;
}