For a given number n, you are asked to calculate the result of Euler’s totient function.

Euler’s totient function calculates the number of integers from 1 to n that are relatively prime to n. Meaning all the numbers with the greatest common divisor with n equal to 1.

Input

The input contains a single integer n (1 ≤ n ≤ ).

Output

The program should print the result of Euler's totient function for n.