“Название задачи можно напевать на мотив марша или строевой песни…”

How many irreducible fractions exist in the interval [0..1] with denominator not exceeding n?

Input

One positive integer n (n < 10001).

Output

Print the number of irreducible fractions in the interval [0..1] with denominator not exceeding n.