求：
\[2^{2^{2^\cdots}}\bmod p \]
多测，\(p\le 10^7,T\le 1000\)
扩展欧拉定理基础题，话说昨天晚上证那个定理证了一晚上还没完全弄明白。。。
众所周知，那个公式是：
\[a^n\equiv a^{n\bmod \varphi(p)+\varphi(p)}\pmod p \]
然后带到这个题的式子里
\[2^{2^{2^\cdots}}\equiv 2^{2^{2^\cdots}\bmod \varphi(p)+\varphi(p)}\pmod p \]
然后，其中这个指数的\(2^{2^\cdots}\bmod \varphi(p)\)部分，和一开始那个要求的式子形式相同，可以递归地求解，然后在递归的过程中模数不断变小
直到\(p=1\)，那么此时答案必为\(0\)，结束递归
然后预处理\(\varphi\)就行
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
LL phi[10000006];
int prime[1000006],notprime[10000006];
inline void get_phi(){
int n=1e7;
phi[1]=1;
for(reg int i=2;i<=n;i++){
if(!notprime[i]) prime[++prime[0]]=i,phi[i]=i-1;
for(reg int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
notprime[i*prime[j]]=1;
if(!(i%prime[j])){
//i mod p=0, phi(i*p)=p*phi(i)
phi[i*prime[j]]=prime[j]*phi[i];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);//i mod p!=0,phi(i*p)=phi(i)*(p-1)
}
}
}
inline LL power(LL a,LL b,LL mod){
LL ret=1;
while(b){
if(b&1) ret=ret*a%mod;
a=a*a%mod;b>>=1;
}
return ret;
}
inline LL work(int p){
if(p==1) return 0;
return power(2,work(phi[p])+phi[p],p);
}
int main(){
get_phi();
int T=read();while(T--) std::printf("%lld\n",work(read()));
return 0;
}