Euler's Phi Function

For given integer n, count the totatives of n, that is, the positive integers less than or equal to n that are relatively prime to n.

Input

n

An integer n (1 ≤ n ≤ 1000000000).

Output

The number of totatives in a line.

Examples

Input

6

Output

2

Input

1000000

Output

400000

inputFormat

Input

n

An integer n (1 ≤ n ≤ 1000000000).

outputFormat

Output

The number of totatives in a line.

Examples

Input

6

Output

2

Input

1000000

Output

400000

样例

1000000

400000