GCDEX  GCD Extreme
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.
Input
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.
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 64bit signed integer.
Example
Input: 10 100 200000 0 Output: 67 13015 143295493160 Time limit has been changed. Some AC solutions get TLE
hide comments
hacker_sk:
20160925 15:54:50
AC in one go :D.. 0.27 sec


mkfeuhrer:
20160815 11:23:29
euler phi :) 

visvats_141095:
20160617 15:05:26
9 tle and finally accepted! learnt a lot from this question! 

raj_394:
20160212 06:28:37
For java.. avoid unnecessary use of long array...Ac in 0.4 :) 

Francky:
20151230 20:15:34
Description updated and corrected. 

iam_ss:
20151225 22:03:02
Welcome to The World Of Number Theory..... Amazing Question!!! 

Deepak :
20151210 19:28:22
very strict time limit..


Ankit Sultana:
20150722 21:59:19
Had to change a few long long's to ints to get AC. Relax the time limit!!! 

Madhav:
20150409 16:01:45
very good question !! 

/* Nitin Jaiman */:
20150323 20:45:48
Same logic passed in c++ but giving TLE in java. 
Added by:  Phenomenal 
Date:  20090216 
Time limit:  0.237s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM World Final Warm up 1  2008 