eolymp
bolt
Try our new interface for solving problems
Problems

Number Theory

Number Theory

Time limit 1 second
Memory limit 128 MiB

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 data

Each line contains one positive integer n (0 < n < 2^31).

Output data

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

Examples

Input example #1
1
6
10
2147000000
Output example #1
0
1
3
1340599805