Solve the programming task below in a Python markdown code block.
For given integer n, count the totatives of n, that is, the positive integers less than or equal to n that are relatively prime to n.



Input


n


An integer n (1 ≤ n ≤ 1000000000).

Output

The number of totatives in a line.

Examples

Input

6


Output

2


Input

1000000


Output

400000