只要用欧拉定理递归下去就好了....
然而还是有些细节没考虑好：
$(P,2) \neq 1$时分解$P=2^k*q$的形式，然后变成$2^k(2^{(2^{2^{...}}-k)\ mod\ phi(P)}\ mod\ P)$，不要掉了$-k$
然而取模的时候别乱取模，比如那个$2^k$不应该取模
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
inline int read(){
char c=getchar();int x=;
while(c<''||c>''){c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x;
}
int P;
inline int phi(int n){
int m=sqrt(n),re=n;
for(int i=;i<=m;i++) if(n%i==){
re=re/i*(i-);
while(n%i==) n/=i;
}
if(n>) re=re/n*(n-);
return re;
}
int Pow(ll a,int b,int P){
ll re=;
for(;b;b>>=,a=a*a%P)
if(b&) re=re*a%P;
return re;
}
int cal(int x){
if(x==) return ;
int k=;
while(~x&) x>>=,k++;
int Phi=phi(x);
int re=(cal(Phi)-k%Phi+Phi)%Phi;
re=Pow(,re,x)%x;
return re<<k;
}
int main(){
freopen("in","r",stdin);
int T=read();
while(T--){
P=read();
printf("%d\n",cal(P)%P);
}
}