The cows have just learned what a primitive root is! Given a prime *p*, a primitive root <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/f203bd9f1553a2d666452cec7d6f1f4f02a817fb.png" style="max-width: 100.0%;max-height: 100.0%;"/> is an integer *x* (1 ≤ *x* &lt; *p*) such that none of integers *x* - 1, *x*<sup class="upper-index">2</sup> - 1, ..., *x*<sup class="upper-index">*p* - 2</sup> - 1 are divisible by *p*, but *x*<sup class="upper-index">*p* - 1</sup> - 1 is. 

Unfortunately, computing primitive roots can be time consuming, so the cows need your help. Given a prime *p*, help the cows find the number of primitive roots <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/f203bd9f1553a2d666452cec7d6f1f4f02a817fb.png" style="max-width: 100.0%;max-height: 100.0%;"/>.
The input contains a single line containing an integer *p* (2 ≤ *p* &lt; 2000). It is guaranteed that *p* is a prime.
#include<bits/stdc++.h>
#define ll long long
#define M 1000000007
#define sz(c) c.size()
#define fr first
#define sc second
#define pb push_back
#define sz(c) c.size()
#define ppb  pop_back
#define all(a)      (a).begin(),(a).end()
#define rep(i,a,n) for( i=a;i<n; i++)
#define what_is(x)  cout << #x << " is " << x << endl;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int TESTS=1;
   // cin>>TESTS;
    while(TESTS--)
    {
        int n,i,j;
        cin>>n;
        int phi=n-1,sum=0;
        rep(i,2,n)
        {
            int prod=1;
            rep(j,1,n)
            {
                prod=(prod*i)%n;
                if(prod==1)
                    break;
            }
            if(j==n-1)
                sum++;
        }
        cout<<sum;
    }
}
