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 >
	visvats_141095: 2016-06-17 15:05:26 9 tle and finally accepted! learnt a lot from this question!
	raj_394: 2016-02-12 06:28:37 For java.. avoid unnecessary use of long array...Ac in 0.4 :)
	Francky: 2015-12-30 20:15:34 Description updated and corrected.
	iam_ss: 2015-12-25 22:03:02 Welcome to The World Of Number Theory..... Amazing Question!!!
	Deepak : 2015-12-10 19:28:22 very strict time limit..
	Ankit Sultana: 2015-07-22 21:59:19 Had to change a few long long's to ints to get AC. Relax the time limit!!!
	Madhav: 2015-04-09 16:01:45 very good question !!
	/* Nitin Jaiman */: 2015-03-23 20:45:48 Same logic passed in c++ but giving TLE in java.
	RISHABH: 2015-02-08 14:44:53 time problem Last edit: 2015-02-08 14:53:39
	Sayak Haldar: 2015-01-24 12:55:53 if you are getting tle, change your long long datatype into int in some places...may be that will help(scanf,printf takes more time while we are dealing with long long)