CF284A.Cows and Primitive Roots

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

奶牛们刚刚学习了什么是原根！给定一个质数 $p$，原根 $\displaystyle x$ 是一个整数 $x$（满足 $1 \le x < p$），使得 $x - 1,\, x^2 - 1,\, \dots,\, x^{p-2} - 1$ 均不能被 $p$ 整除，但 $x^{p-1} - 1$ 能被 $p$ 整除。

遗憾的是，计算原根可能非常耗时，因此奶牛们需要你的帮助。给定一个质数 $p$，请帮助奶牛们求出原根的个数 $\displaystyle \varphi(p-1)$。

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

输入包含一行，其中有一个整数 $p$（$2 \leq p < 2000$）。保证 $p$ 是一个质数。

Output on a single line the number of primitive roots .

在一行中输出原根的个数 。

The only primitive root is 2.

The primitive roots are 2 and 3.

唯一的原根 是 2。

模 的原根是 2 和 3。