我们想知道 \(2^{2^{2^\cdots}}\mod p\)。
考虑用扩展欧拉定理降幂，
\[2^{2^{2^\cdots}}\equiv 2^{(2^{2^\cdots}\mod \varphi(p))+\varphi(p)}\mod p. \]
于是定义\(f(p)=2^{2^{2^\cdots}}\mod p\)。
则
\[f(p)\equiv 2^{f(\varphi(p))+\varphi(p)} \mod p.\]
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll T, p;
ll getPhi(ll x){
ll ans=x;
for(int i=2; i*i<=x; i++)
if(x%i==0){
ans -= ans / i;
while(x%i==0) x /= i;
}
if(x>1) ans -= ans / x;
return ans;
}
ll ksm(ll a, ll b, ll c){
ll re=1;
while(b){
if(b&1) re = (re * a) % c;
a = (a * a) % c;
b >>= 1;
}
return re;
}
ll f(ll x){
if(x==1) return 0;
ll phi=getPhi(x);
return ksm(2, f(phi)+phi, x);
}
int main(){
cin>>T;
while(T--){
scanf("%lld", &p);
printf("%lld\n", f(p));
}
return 0;
}