Time Limit: 1 s
Memory Limit: 128 MB

Submission：8
AC：7
Score：99.56

Given *n*, a positive integer, how many positive integers less than *n* are relatively prime to *n*? Two integers *a* and *b* are relatively prime if there are no integers *x > 1, y > 0, z > 0* such that *a = xy* and *b = xz*.

There are several test cases. For each test case, standard input contains a line with *n <= 1,000,000,000*. A line containing 0 follows the last case.

For each test case there should be single line of output answering the question posed above.

input

7
12
0

output

6
4