Compute \(\varphi(n)\), the number of integers in \([1,n]\) that are coprime with \(n\).

Input

One positive integer \(n\).

The input satisfies:

• \(1 <= n <= 10^12\)

Output

Print \(\varphi(n)\).

Example

Input

55

Output

40