e-olymp
Competitions

Power + Euler function

My favorite, irreducible...

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

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.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
5
Output example #1
9