In number theory, the totient $\Phi$ of a positive integer N is defined as the number of positive integers less than or equal to N that are co-prime to N.

Given an integer N. Compute the value of the totient $\Phi$.

Input:
First and the only line of input contains single integer N.

Output:
Print the $\Phi (N)$ in a single line.

Constraints:
$1 \le N \le 1000000$