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

НСД Супер-екстрім

НСД Супер-екстрім

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

Маючи задані значення n Ви повинні обчислити значення G. Визначення для G наведено нижче:

Тут 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);}/* Тут GCD() позначає функцію знаходження найбільшого спільного дільника двох чисел */

Вхідні дані

Вхідний файл складається не більше ніж зі 100 рядків вхідних даних. Кожен рядок містить єдине натуральне число n (1 < n < 4000001). Зміст числа n наведено в описі задачі. Вхідні дані завершуються рядком, який містить нуль. Цей рядок не повинен опрацьовуватись.

Вихідні дані

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

Приклад

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