id=1284">http://poj.org/problem?id=1284

typedef long long ll;

using namespace std;

/*

    求原根

    g^d ≡ 1(mod p) 当中d最小为p-1。g 便是一个原根

    复杂度：O(m)*log（P-1）（m为p-1的质因子个数）

*/

ll euler(ll x) {

    ll res = x;

    for (ll i = 2; i <= x / i; i++) if (x % i == 0) {

        res = res / i * (i - 1);

        while(x % i == 0) x /= i;

    }

    if (x > 1) res = res / x * (x - 1);

    return res;

}

int main () {

    ll n;

    while(~scanf("%lld", &n)) {

        printf("%lld\n", euler(n - 1));

    }

    return 0;

}