Знаменатель

Найдите количество правильных дробей, у которых знаменатель не превышает $n$.

Дробь $\frac{a}{b}$ считается правильной, если выполняются следующие условия:

1. $a$ и $b$ — положительные целые числа;

2. $a\le b$;

3. наибольший общий делитель чисел $a$ и $b$ равен $1$.

Входные данные

Первая строка содержит одно целое число $n$ ($1\le n\le 10^6$).

Выходные данные

Выведите одно целое число — ответ на задачу.

Примеры

Оценивание

1. ($30$ баллов): $n\le 10^3$;

2. ($40$ баллов): $n\le 10^5$;

3. ($30$ баллов): без дополнительных ограничений.