Competitions

# Power + Euler function

# 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 denominator **n**.

#### Input

Each line is a separate test case that contains one integer **n** (**n** < `10`

). The last line contains ^{9}**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 answer to the problem.

Input example #1

12 123456 7654321 0

Output example #1

4 41088 7251444