GCD Extreme

Time Limit: 500 ms Memory Limit: 262144 KiB

Problem Description

Given the value of n, you will have to find the value of G. 
The definition of G is given below:
 
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 100 lines of inputs. Each line contains an integer n (1<n<8000001). The meaning of n is given in the problem statement. Input is terminated by a line containing a single zero. 

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.

Sample Input

10
100
200000
0

Sample Output

67
13015
143295493160

Hint

 

Source

SDUST