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>

using namespace std;



/********************************************************************/
#define M1 1000000007	//Standard primes used in modulo operations
#define M2 998244353
#define ll long long
#define FOR(i, a, b) for(int i=a;i<b;i++)
#define REV(i, b, a) for(int i=b-1;i>=a;i--)
#define ff first
#define ss second
#define pb push_back
#define mop make_pair
#define ce(ele) cout<<ele<<' '
#define cs(ele) cout<<ele<<endl
#define CASE(t) ll t; cin>>t; while(t--)
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define gf vector<vector<int>>
void FAST() {	//FAST Input Output, DONT use both scnaf,printf / cin,cout , Use any ONE system
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
ll gcd(ll x, ll y) {	//returns gcd of two long long ints
	if (x == 0) return y;
	return gcd(y % x, x);
}

ll powM(ll x, ll y, ll m) {	//returns (a^b)%m ( ^ is exponent )
	ll ans = 1, r = 1;
	x %= m;
	while (r > 0 && r <= y)
	{
		if (r & y)
		{
			ans *= x;
			ans %= m;
		}
		r <<= 1;
		x *= x;
		x %= m;
	}
	return ans;
}
template<typename T>
void printarr(vector<T> arr){
	FOR(i,0,arr.size()) cout << arr[i] << " ";
	cout<<endl;
}

template<typename T>
void printarr2d(vector<vector<T>> arr){
	int n = arr.size();

	FOR(i,0,n){
        int m = arr[i].size();
		FOR(j,0,m){
			cout << arr[i][j] << " ";

		}
		cout<<endl;
	}
}


map<long long, long long> factorize(long long n) {	//returns map containing factor and multiplicity, Eg: 60 = {{2,2},{3,1},{5,1}}
	map<long long, long long> ans;
	for (long long i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ans[i]++;
			n /= i;
		}
	}
	if (n > 1) {
		ans[n]++;
		n = 1;
	}
	return ans;
}

vector<bool> sieve(){
	int n = 1e6;
	vector<bool> prime(n+1,true);	
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
	return prime;
}


/*************************************************DEBUGGING*****************************************************************/

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif



/***************************************************GRAPH_ALGOS************************************************************/

template<typename T>
void add_edge(vector<vector<T>> &graph, T u, T v){
    // from u to v
    graph[u].pb(v);
    // comment out bottom line for directed graphs
    graph[v].pb(u);
}

template<typename T>
void printgraph(vector<vector<T>> arr){
	int n = arr.size();
	FOR(i,0,n){
        int m = arr[i].size();
        cout <<i<<": ";
		FOR(j,0,m){            
			cout << arr[i][j] << " ";
		}
		cout<<endl;
	}
}
template<typename T>
void dfs(vector<bool> &visited, vector<vector<T>> &adj, T v) { // v is starting vertex
    visited[v] = true;
    //cout << v <<" ";
    for (T u : adj[v]) {
        if (!visited[u])
            dfs(visited, adj, u);
    }
}


template<typename T>
vector<T> bfs(vector<bool> &visited, vector<vector<T>> &graph, T start_node){
    queue<T> q; 
    q.push(start_node);
    visited[start_node] = true; 
	vector<T> prev(graph.size() + 1); // for shortest path

    while (!q.empty()) { 
        T current_node = q.front();
        q.pop(); 
        //cout << f << " "; 
        // Enqueue all adjacent of f and mark them visited
        for (auto next : graph[current_node]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
				prev[next] = current_node; // for shortest path
            }
        }
    }
	// uncomment for shortest path
	return prev; 
}


/***************************************************LESGOOOOO************************************************************/


int main() {
	FAST();
	//freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ll int n; cin >> n;

	return 0;
}