A Lack of Common Divisors

Given a positive integer $N$, determine how many of the integers between 1 and $N$ are co-prime with $N$.

Two numbers are co-prime if the only common positive factor of the two numbers is 1.

Input

The input will contain one integer $N$ ($0 < N < 10000000$).

Output

Print a single integer--the number of integers between 1 and $N$ that are co-prime with $N$.

Samples

Input	Output
15	8

Input	Output
20	8