Jennie

首先我们要知道欧拉定理

$a^bequiv^{b%phi(p)+phi(p)}quad b>=p$

$a^bequiv^{b%phi(p)} quad b<p$

然后对于这个式子，我们可以改造成

$2^{2^{2^{2^{...}}}%phi(p)+phi(p)}$

显然肯定是满足1的

然后这样p就成了$phi(p)$

直到$phi(p)=1$时，式子为0

然后一层层往外推

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int t;int p;
int phi[10000005];
int prime[1000005];
int pp;
bool vis[10000005];
void ini(){
    for(int i=2;i<=10000005;++i){
        if(!vis[i]){
            prime[++pp]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=pp&&i*prime[j]<=10000005;++j){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }else{
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}
int pow(int x,int mi,int ppp){
    int ans=1;
    while(mi){
        if(mi&1){
            ans*=x;
            ans%=ppp;
        }
        x*=x;
        x%=ppp;
        mi>>=1;
    }
    return ans;
}
int solve(int x){
    if(x==1) return 0;
    return pow(2,solve(phi[x])+phi[x],x);
}
signed main(){
    scanf("%d",&t);
    ini();
    while(t--){
        scanf("%d",&p);
        cout<<solve(p)<<endl;
    }
    return 0;
}