Problems

# GCD Extreme

# GCD Extreme

Given the value of **n**, you have to find the value of **G**, where

Here **GCD**(**i, j**) means the greatest common divisor of integer **i** and integer **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); } /*Here GCD() is a function that finds the greatest common divisor of the two input numbers*/ |

**Input**

The input file contains at most **20000** lines of inputs. Each line contains an integer **n** (**1** < **n** < **200001**). The last line contains **n** = **0** and is not processed.

**Output**

For each line of input produce one line of output. This line contains the value of **G** for the corresponding **n**. The value of **G** will fit in a **64**-bit signed integer.

Input example

10 100 20000 0

Output example

67 13015 1153104356