【题目描述】

输入正整数N，求G的值。G如下定义：

这里GCD(i,j)代表i,j的最大公约数。

对于不理解求和符号的人，下面给出了G的代码表示：

G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
    G+=gcd(i,j);
}
/*gcd(i,j)的值是i,j的最大公约数*/

【输入格式】

输入包含至多100组数据。每组数据占一行，包含正整数N(2<=N<=1<N<4000000)。输入以N=0结束。

【输出格式】

对于每组数据，输出一行，即所对应的G值。答案保证在64位带符号整数范围内。

【样例输入】

10
100
200000
0

【样例输出】

67
13015
143295493160

【提示】

对于30%的数据，2<=N<=2000

对于100%的数据，2<=N<=4000000

【来源】

UVa11426 GCD - Extreme (II)

刘汝佳，《算法竞赛入门经典训练指南》表2.4