Problems
Again irreducible
Again irreducible
The fraction $m / n$ is called regular irreducible, if $0 < m < n$ and $GCD(m, n) = 1$. Find the number of regular irreducible fractions with the denominator $n$.
\InputFile
Each line is a separate test case that contains one integer $n~(n < 10^9)$. The last line contains $0$ and is not processed. The number of test cases is no more than $100$.
\OutputFile
For each value of $n$ print in a separate line the answer to the problem.
Input example #1
12 123456 7654321 0
Output example #1
4 41088 7251444