e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Euler Function

Number Theory

For the given positive integer n find the number of integers m, such that 1mn, gcd(m, n) ≠ 1 and gcd(m, n) ≠ m. gcd is an abbreviation for "greatest common divisor".

Input

Each line contains one positive integer n (0 < n < 231).

Output

For each number n print the number of required integers m.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1
6
10
2147000000
Output example #1
0
1
3
1340599805