GCD Extreme II

For a given $n$ calculate the value of $G$, where

Here $GCD(i,j)$ means the greatest common divisor of integers $i$ and $j$.

For those who have trouble understanding summation notation, the meaning of $G$ is given in the following code:

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

Input

Consists of no more than $20000$ lines. Each line contains one integer $n(1<n\le 4\cdot 10^6)$. Input is terminated by a line containing a single zero and should not be processed.

Output

For each input number $n$ print in a separate line the corresponding value of $G$. The value of $G$ fits in a $64$-bit signed integer.

Examples