https://www.luogu.com.cn/record/list?pid=P4139&user=510555 可以看到全是CE。

但神奇的是，本地用dev可以过编，甚至能跑样例，实在不知道是什么问题……

代码：

#include<bits/stdc++.h>
#define int1 int
#define N 10000000
#define M 1000000
using namespace std;
int1 q,n,x,y,z,i,j,cnt,phi[N + 5] = {0,1},prime[M + 5];
bool not_prime[N + 5];
int1 read(){//快读 
	int1 x = 0,f = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-'){
			f = -1;
		}
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ '0');
		ch = getchar();
	}
	return x * f;
}
void print(int1 x){//快写 
  	if(x < 0){
    	putchar('-');
    	x = -x;
  	}
  	if(x > 9){
    	print(x / 10);
  	}
  	putchar(x % 10 ^ 48);
  	return ;
}
void ps(int1 x){
	print(x);
	putchar(' ');
	return ;
}
void pe(int1 x){
	print(x);
	putchar('\n');
	return ;
}
int1 quick_pow(int1 a,int1 b,int1 m){//快速幂 
	int1 s = 1;
	while(b){
		if(b & 1){
			s = 1ll * s * a % m;
		}
		a = 1ll * a * a % m;
		b >>= 1;
	}
	return s;
}
int1 f(int1 x){//用扩展欧拉定理递归求解 
	if(x == 1){
		return 0;
	}
	y = f(phi[x]);
	z = quick_pow(2,y + phi[x],x);
//	cout<< x << " " << phi[x] << " " << y << " " << z << endl;
	return z;
}
int main(){
	n = 10000000;
	//这里开始是欧拉筛 
	not_prime[1] = 1;
	for(i = 2; i <= n; i++){
		if(!not_prime[i]){
			prime[++cnt] = i;
			phi[i] = i - 1;
		}
		for(j = 1; j <= cnt && i * prime[j] <= n; j++){
			not_prime[i * prime[j]] = 1;
			if(!(i % prime[j])){
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}else{
				phi[i * prime[j]] = phi[i] * phi[prime[j]];
			}
		}
	}
	q = read();
	while(q--){//处理每次询问 
		pe(f(read()));
	}
	return 0;
}