GCDEX - GCD Extreme

### 题目描述 得定 $n$ ，求 $$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\gcd(i,j)$$ 其中 $\gcd(i,j)$ 指的是 $i$ 和 $j$ 的最大公约数。 ### 输入格式 **本题有多组数据。** 对于每组数据，输出一个整数 $n$ ，如果 $n=0$ 就终止程序。 ### 输出格式 对于每组数据，输出计算结果。 ### 说明 / 范围 对于 $100\%$ 的数据，$1 \le n \le 10^6$，不超过 $20000$ 组数据。

Given the value of N, you will have to find the value of G. 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.

The input file contains at most 20000 lines of inputs. Each line contains an integer N (1 < N < 1000001). The meaning of N is given in the problem statement. Input is terminated by a line containing a single zero.

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.

10
100
200000
0

67
13015
143295493160

Time limit has been changed. Some AC solutions get TLE