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