Given a natural number
\(n <= 10^9,\) determine the number of natural numbers less than
\(n\ ) and coprime to
\(n\). This number is denoted by
\( f(n) \) and is called Euler's phi function. The complexity of the algorithm should be
\( O(\sqrt{n})\) .
Input
The input is a natural number
n.
Imprint
Print the answer to the problem.
Examples