GCD

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

prb1146

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*/

Specifications

Input

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

Output

For each input integer n print in a separate line the corresponding value of G.

Problem information

Time Limit: 2 seconds
Memory Limit: 64 MB
Balls for the passed test: 10
Complexity: 13% 228/262
Classes: Number theory, GCD, LCM

Example

Example input

Example output

67
13015
442011

← UnfairDivision

Problems

GCD Extreme →