eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

НСД Екстрім 2

НСД Екстрім 2

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

За заданим n обчислити значення G, де

G = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} GCD(i,j)

Через GCD(i, j) позначено найбільший спільний дільник цілих чисел i та j.

Для тих, хто не зустрічався зі знаком суми пояснюємо, що значення G формально по наведеній формулі обчислюється за допомогою коду:

g = 0;
for (i = 1; i < n; i++)
for (j = i + 1; j <= n; j++)
  g += gcd(i, j);

Вхідні дані

Складається не більше ніж з 20000 рядків. Кожен рядок містить одне ціле число n~(1 < n \le 4 \cdot 10^6). Останній рядок містить n = 0 та не обробляється.

Вихідні дані

Для кожного вхідного значення n вивести в окремому рядку відповідне значення G. Значення G вміщується у 64-бітове знакове ціле число.

Приклад

Вхідні дані #1
6
10
100
200000
0
Вихідні дані #1
20
67
13015
143295493160