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

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

Output

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