#include <bits/stdc++.h>
using namespace std;
long long int pov(long long int j, long long int i, long long int n) {
  long long int p = 1;
  while (i--) {
    p = (p * j) % n;
  }
  return p;
}
void solve() {
  long long int i, j, n, count = 0;
  cin >> n;
  for (j = 1; j < n; j++) {
    long long int p = 1;
    long long int a[n - 1];
    i = 0;
    while (i < n - 1) {
      p = (p * j) % n;
      a[i] = p;
      i++;
    }
    for (i = n - 1; i > 0; i--) {
      if (i == n - 1) {
        long long int k = (a[i - 1] - 1);
        if (k % n == 0)
          continue;
        else
          break;
      } else {
        long long int k = (a[i - 1] - 1);
        if (k % n != 0)
          continue;
        else
          break;
      }
    }
    if (i == 0) count++;
  }
  cout << count;
  return;
}
int main() {
  solve();
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

The cows have just learned what a primitive root is! Given a prime p, a primitive root <image> is an integer x (1 ≤ x < p) such that none of integers x - 1, x2 - 1, ..., xp - 2 - 1 are divisible by p, but xp - 1 - 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 <image>.

Input

The input contains a single line containing an integer p (2 ≤ p < 2000). It is guaranteed that p is a prime.

Output

Output on a single line the number of primitive roots <image>.

Examples

Input

3


Output

1


Input

5


Output

2

Note

The only primitive root <image> is 2.

The primitive roots <image> are 2 and 3.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long int pov(long long int j, long long int i, long long int n) {
  long long int p = 1;
  while (i--) {
    p = (p * j) % n;
  }
  return p;
}
void solve() {
  long long int i, j, n, count = 0;
  cin >> n;
  for (j = 1; j < n; j++) {
    long long int p = 1;
    long long int a[n - 1];
    i = 0;
    while (i < n - 1) {
      p = (p * j) % n;
      a[i] = p;
      i++;
    }
    for (i = n - 1; i > 0; i--) {
      if (i == n - 1) {
        long long int k = (a[i - 1] - 1);
        if (k % n == 0)
          continue;
        else
          break;
      } else {
        long long int k = (a[i - 1] - 1);
        if (k % n != 0)
          continue;
        else
          break;
      }
    }
    if (i == 0) count++;
  }
  cout << count;
  return;
}
int main() {
  solve();
  return 0;
}

```