#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 4e2 + 4;
constexpr int MAXK = 1e5 + 5;
constexpr int MOD = 1e9 + 7;
constexpr long long INF = 9187201950435737471;
constexpr int LOG = 11;
int n, m, ans;
int mul(int a, int b) { return 1ll * a * b % m; }
int pwr(int a, int b) {
  if (!b) {
    return 1;
  }
  int tmp = pwr(a, b / 2);
  tmp = mul(tmp, tmp);
  if (b & 1) {
    tmp = mul(tmp, a);
  }
  return tmp;
}
bool Check(int a, int b) {
  int x = pwr(a, b) - 1;
  if (b == n - 1) {
    return (x == 0);
  }
  return (x != 0);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  m = n;
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < n; j++) {
      if (!Check(i, j)) {
        break;
      } else if (j + 1 == n) {
        ans++;
      }
    }
  }
  cout << ans;
  return 0;
}

### Prompt

Create a solution in cpp for 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;
constexpr int MAXN = 4e2 + 4;
constexpr int MAXK = 1e5 + 5;
constexpr int MOD = 1e9 + 7;
constexpr long long INF = 9187201950435737471;
constexpr int LOG = 11;
int n, m, ans;
int mul(int a, int b) { return 1ll * a * b % m; }
int pwr(int a, int b) {
  if (!b) {
    return 1;
  }
  int tmp = pwr(a, b / 2);
  tmp = mul(tmp, tmp);
  if (b & 1) {
    tmp = mul(tmp, a);
  }
  return tmp;
}
bool Check(int a, int b) {
  int x = pwr(a, b) - 1;
  if (b == n - 1) {
    return (x == 0);
  }
  return (x != 0);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  m = n;
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < n; j++) {
      if (!Check(i, j)) {
        break;
      } else if (j + 1 == n) {
        ans++;
      }
    }
  }
  cout << ans;
  return 0;
}

```