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$.

Input

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$.

Output

For each value of $n$ print in a separate line the number of regular irreducible fractions with the denominator $n$.

Examples