Задачі
НСД Екстрім 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