// Calculate all Phi(x) form 2 to MAX_N
// This code took less than 0.5s to calculate with MAX_N = 10^7
const int MAX_N = 10000000;
int phi[MAX_N];
bool pr[MAX_N];
void totient() {
    for (int i = 0; i < MAX_N; i++) phi[i] = i, pr[i] = true;
    for (int i = 2; i < MAX_N; i++) if (pr[i]) {
        for (int j = i; j < MAX_N; j += i) pr[j] = false, phi[j] = phi[j] - (phi[j] / i);
        pr[i] = true;
    }
}