Hide

# Relatives

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 \ge 2, y \ge 1, z \ge 1$ such that $a = xy$ and $b = xz$.

## Input

There up to $10$ test cases. For each test case, standard input contains a line with $1\leq n \leq 1\, 000\, 000\, 000$. A line containing $0$ follows the last case.

## Output

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

Sample Input 1 Sample Output 1
7
12
0

6
4

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 3.8medium
Statistics Show