Again irreducible

Input

Each line is a separate test case and contains one integer $n$ (n < 10^9). The last line contains $0$ and is not processed. The number of test cases does not exceed $100$.

Output

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

Examples