Задачи
НОД Экстрим 2
НОД Экстрим 2
По заданному значению $n$ вычислить значение $G$, где
$$
G = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} GCD(i,j)
$$
Через $GCD(i, j)$ обозначен наибольший общий делитель целых чисел $i$ и $j$.
Для тех, кто не встречался со знаком суммирования объясняем, что значение $G$ формально по приведённой формуле вычисляется при помощи следующего кода:
\begin{center}
\begin{lstlisting}[language=C++]
g = 0;
for (i = 1; i < n; i++)
for (j = i + 1; j <= n; j++)
g += gcd(i, j);
\end{lstlisting}
\end{center}
\InputFile
Состоит из не более чем $20000$ строк. Каждая строка содержит одно натуральное число $n~(1 < n \le 4 \cdot 10^6)$. Последняя строка содержит $n = 0$ и не обрабатывается.
\OutputFile
Для каждого входного значения $n$ вывести в отдельной строке соответствующее значение $G$. Значение $G$ помещается в $64$-битовое знаковое целое число.
Входные данные #1
6 10 100 200000 0
Выходные данные #1
20 67 13015 143295493160