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 >
	王泽宇: 2014-03-13 08:41:28 Practice mathematics!
	Guilherme Sena: 2014-03-07 22:14:20 ATTENTION: MAXIMAL N = 1000000!!!
	Piyush Raman Srivastava: 2014-01-24 20:42:15 so much to understand for this problem!! :-/ Taught me how things relate to each other in mathematics!! :) Last edit: 2014-01-25 14:14:48
	hahaha: 2013-11-27 08:31:03 Time limit is too strict got AC in UVA but get TLE here
	$iddharth prasad: 2013-09-21 09:15:45 getting tle how to optimize ??
	YangYue: 2012-12-07 08:19:57 O(n) can solve it
	Renato Ferreira: 2012-07-10 17:39:21 Optimization tips: do not overuse long long and read the whole input using fread, then parse the integers.
	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~