#include <cstdio>const int N = 10000000;bool vis[N];int pr[N], phi[N], mu[N];void init() { mu[1] = phi[1] = 1; for(int i = 2; i < N; i ++ ) { if(!vis[i]) pr[++*pr] = i, phi[i] = i-1, mu[i] = -1; for(int j = 1; j <= *pr && i*pr[j] < N; j ++ ) { vis[i*pr[j]] = 1; if(i%pr[j]) { phi[i*pr[j]] = phi[i]*pr[j]; break; } mu[i*pr[j]] = -mu[i]; phi[i*pr[j]] = phi[i]*phi[pr[j]]; } }}int main() { init();}