Знаменник

Знайдіть кількість правильних дробів, у яких знаменник не перевищує $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$ балів): без додаткових обмежень.