SPOJ Problem Set (classical) 3871. GCD Extreme Problem code: GCDEX

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(k=i;k< N;k++)

for(j=i+1;j<=N;j++)

{

G+=gcd(k,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 (1Output

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.

Example

Input:
10
100
200000
0

Output:
67
13015
143295493160

Time limit has been changed. Some AC solutions get TLE

---

Added by:	Phenomenal
Date:	2009-02-16
Time limit:	3s
Source limit:	50000B
Languages:	All except: CLOJ ERL F# JS PERL 6 TECS
Resource:	ACM World Final Warm up 1 - 2008