Compute \(phi(n)\), the number of integers from \(1\) through \(n\) that are coprime with \(n\).

Input

One line containing \(n\).

The input satisfies:

• \(1 \le n \le 10^12\)

Output

Print \(phi(n)\).

Example

Input

15845

Output

12672