const int N = 1e6 + 5;
int isnt[N], prime[N], cnt;;
void sieve(int n) {
    isnt[1] = isnt[0] = true;
    for(int i = 2; i <= n; i++) {
        if(!isnt[i]) {
            prime[++cnt] = i;
        }
        for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            isnt[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

int Euler(int x) {
    if(x == 1) return 1;
    int res = x;
    for(int i = 1; i <= cnt && prime[i] * prime[i] <= x; i++) {
        if(x % prime[i] == 0) res = res / prime[i] * (prime[i] - 1);
        while(x % prime[i] == 0) x /= prime[i];
    }
    // return x > 1 ? res / x * (x - 1) : res;
    // return x > 1 ? x - 1 : res;
    return x > 1 ? res / x * (x - 1) : res;
}