Problems
Number Theory
Number Theory
For the given positive integer n find the number of integers m, such that 1 ≤ m ≤ n, 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