Problems
GCD Super-Extreme
GCD Super-Extreme
Given the value of \textbf{n}, you will have to find the value of \textbf{G}. The definition of \textbf{G} is given below:
\includegraphics{https://static.e-olymp.com/content/53/53630f1afe7320d524271dd744a552787cd2966c.jpg}
Here \textbf{GCD}(\textbf{i, j}) means the greatest common divisor of integer \textbf{i} and integer \textbf{j}.
For those who have trouble understanding summation notation, the meaning of \textbf{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);\}/*Here GCD() is a function that finds the greatest common divisor of the two input numbers*/
\InputFile
The input file contains at most \textbf{20000} lines of inputs. Each line contains an integer \textbf{n} (\textbf{1} < \textbf{n} < \textbf{4000001}). The meaning of \textbf{n} is given in the problem statement. Input is terminated by a line containing a single zero. This zero should not be processed.
\OutputFile
For each line of input produce one line of output. This line contains the value of \textbf{G} for the corresponding \textbf{n}. The value of \textbf{G} will fit in a \textbf{64}-bit signed integer.
Input example #1
10 100 200000 0
Output example #1
67 13015 143295493160