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 64-bit signed integer.

Example

Input:
10
100
200000
0

Output:
67
13015
143295493160

Time limit has been changed. Some AC solutions get TLE.

---

hide comments

< Previous 1 2 3 4 5 Next >
	Mitch Schwartz: 2011-10-27 09:19:54 Here is a currently working link to the problem on UVa Online Judge: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2421 @purav: Yes, UVa uses these letters for(i=1;i<N;i++) for(j=i+1;j<=N;j++) G+=gcd(i,j); Last edit: 2011-10-27 09:20:52
	张钧瑞: 2011-07-27 08:44:12 A good problem~
	sandeep pandey: 2011-06-06 16:27:57 time limit is too strict! try optimization in calculation of phi:-) Last edit: 2011-07-17 12:29:39
	purav: 2010-05-18 13:43:08 for(k=i;k< N;k++) for(j=i+1;j<=N;j++) here, what is i? shud it not be like this? for(k=1;k< N;k++) for(j=k+1;j<=N;j++)
	Ravi Kiran: 2010-04-07 06:40:47 Can be done without using phi values!And in much quicker time,because of the same! :)
	~ adieus ~: 2009-09-11 09:26:11 O(n^(3/2)) wont work ?? Yeah it doesnt, we need a Pure sieve's implementation for getting phi values. very easy optimizations to my logic has got AC :) Last edit: 2009-09-11 11:43:41
	.:: Pratik ::.: 2009-06-14 15:22:13 got ACC on UVA in 0.032s but TLE here :( Last edit: 2009-06-14 15:22:30
	zhengxi: 2009-03-12 17:52:13 correct task: http://icpcres.ecs.baylor.edu/onlinejudge/external/114/11424.html the only difference is bigger maximal N (about 1000000 instead of 200000 there) Last edit: 2009-03-12 17:52:13
	[Trichromatic] XilinX: 2009-03-07 15:00:10 The problem setter has been banned for his cheating actions. To see the original description, you may go to UVa Online Judge(http://icpcres.ecs.baylor.edu) and find that problem(id:11426).