Знайдіть кількість правильних дробів, у яких знаменник не перевищує n.
Дріб ba називається правильним, якщо
a, b — цілі додатні числа;
a≤b;
найбільший спільний дільник a та b — 1.
Перший рядок містить одне ціле число n (1≤n≤106).
Виведіть одне ціле число — відповідь на задачу.
(30 балів): n≤103;
(40 балів): n≤105;
(30 балів): без додаткових обмежень.