bool vis[N]; //质数为0
int prime[N], phi[N];  //一个存质数，一个是欧拉函数
void get_prime(){
    int pos = 0;
    phi[1] = 1;
    vis[1] = 1;
    for(ll i = 2; i <= N; i++){
        if(!vis[i]){
            prime[++pos] = i;
            phi[i] = i-1;
        }
        for(ll j = 1; j <= pos && prime[j]*i <= N; j++){
            vis[i*prime[j]] = 1;
            if(i%prime[j] == 0){
                phi[i*prime[j]] = phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]] = phi[i]*phi[prime[j]];
        }
    }
}