#include <bits/stdc++.h> // NeOWami
using namespace std;
#define int long long
 
int eulerPhi(int n) { // = n (1-1/p1) ... (1-1/pn)
    if (n == 0) return 0;
    int ans = n;
    for (int x = 2; x*x <= n; ++x) {
        if (n % x == 0) {
            ans -= ans / x;
            while (n % x == 0) n /= x;
        }
    }
    if (n > 1) ans -= ans / n;
    return ans;
}
 
const int N = 1e6 + 5;
int euler[N];
 
bool prime[N];
/*
int phi[N], isPrime[N];
void sieve(int n) {
    for (int i = 1; i <= n; i++) phi[i] = i;
    for (int i = 2; i <= n; i++) if (!isPrime[i]) {
        for (int j = i * i; j <= n; j += i) isPrime[j] = 1;
        for (int j = i; j <= n; j += i) phi[j] -= phi[j] / i;
    }
    phi[1] = 0;
}
*/
void sieve(){
    for (int i = 0; i < N; i++) euler[i] = i;
 
    prime[0] = prime[1] = 1;
    for (int i = 2; i * i < N; i++){
        if (!prime[i]){
            for (int j =  i * i; j < N; j += i){
                prime[j] = true;
            }
        }
    }
 
    for (int i = 1; i < N; i++){
        if (!prime[i]){
            // euler[i]--;
            for (int j = i; j < N; j += i){
                euler[j] -= euler[j] / i;
            }
        }
    }
    euler[1] = 0;
}
 
signed main() {
    cin.tie(NULL)->sync_with_stdio(false);
    if(ifstream("Input.inp")) {
        freopen("Input.inp", "r", stdin);
        freopen("Output.out", "w", stdout);
    }
 
    sieve();
 
    for (int i = 1; i < 100; i++){
        cerr << i << " " << eulerPhi(i) << " " << euler[i] << "\n";
    }
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+IC8vIE5lT1dhbWkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBpbnQgbG9uZyBsb25nCgppbnQgZXVsZXJQaGkoaW50IG4pIHsgLy8gPSBuICgxLTEvcDEpIC4uLiAoMS0xL3BuKQogICAgaWYgKG4gPT0gMCkgcmV0dXJuIDA7CiAgICBpbnQgYW5zID0gbjsKICAgIGZvciAoaW50IHggPSAyOyB4KnggPD0gbjsgKyt4KSB7CiAgICAgICAgaWYgKG4gJSB4ID09IDApIHsKICAgICAgICAgICAgYW5zIC09IGFucyAvIHg7CiAgICAgICAgICAgIHdoaWxlIChuICUgeCA9PSAwKSBuIC89IHg7CiAgICAgICAgfQogICAgfQogICAgaWYgKG4gPiAxKSBhbnMgLT0gYW5zIC8gbjsKICAgIHJldHVybiBhbnM7Cn0KCmNvbnN0IGludCBOID0gMWU2ICsgNTsKaW50IGV1bGVyW05dOwoKYm9vbCBwcmltZVtOXTsKLyoKaW50IHBoaVtOXSwgaXNQcmltZVtOXTsKdm9pZCBzaWV2ZShpbnQgbikgewogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSBwaGlbaV0gPSBpOwogICAgZm9yIChpbnQgaSA9IDI7IGkgPD0gbjsgaSsrKSBpZiAoIWlzUHJpbWVbaV0pIHsKICAgICAgICBmb3IgKGludCBqID0gaSAqIGk7IGogPD0gbjsgaiArPSBpKSBpc1ByaW1lW2pdID0gMTsKICAgICAgICBmb3IgKGludCBqID0gaTsgaiA8PSBuOyBqICs9IGkpIHBoaVtqXSAtPSBwaGlbal0gLyBpOwogICAgfQogICAgcGhpWzFdID0gMDsKfQoqLwp2b2lkIHNpZXZlKCl7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgZXVsZXJbaV0gPSBpOwoKICAgIHByaW1lWzBdID0gcHJpbWVbMV0gPSAxOwogICAgZm9yIChpbnQgaSA9IDI7IGkgKiBpIDwgTjsgaSsrKXsKICAgICAgICBpZiAoIXByaW1lW2ldKXsKICAgICAgICAgICAgZm9yIChpbnQgaiA9ICBpICogaTsgaiA8IE47IGogKz0gaSl7CiAgICAgICAgICAgICAgICBwcmltZVtqXSA9IHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgZm9yIChpbnQgaSA9IDE7IGkgPCBOOyBpKyspewogICAgICAgIGlmICghcHJpbWVbaV0pewogICAgICAgICAgICAvLyBldWxlcltpXS0tOwogICAgICAgICAgICBmb3IgKGludCBqID0gaTsgaiA8IE47IGogKz0gaSl7CiAgICAgICAgICAgICAgICBldWxlcltqXSAtPSBldWxlcltqXSAvIGk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBldWxlclsxXSA9IDA7Cn0KCnNpZ25lZCBtYWluKCkgewogICAgY2luLnRpZShOVUxMKS0+c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGlmKGlmc3RyZWFtKCJJbnB1dC5pbnAiKSkgewogICAgICAgIGZyZW9wZW4oIklucHV0LmlucCIsICJyIiwgc3RkaW4pOwogICAgICAgIGZyZW9wZW4oIk91dHB1dC5vdXQiLCAidyIsIHN0ZG91dCk7CiAgICB9CiAgICAKICAgIHNpZXZlKCk7CgogICAgZm9yIChpbnQgaSA9IDE7IGkgPCAxMDA7IGkrKyl7CiAgICAgICAgY2VyciA8PCBpIDw8ICIgIiA8PCBldWxlclBoaShpKSA8PCAiICIgPDwgZXVsZXJbaV0gPDwgIlxuIjsKICAgIH0KICAgIHJldHVybiAwOwp9