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 >
	whyamievenhere: 2018-12-19 20:02:17 TLE is killing me here... time limit is really ridiculous,
	badboy_1496: 2018-07-17 06:08:56 hurray!!!! ac in one go...nice way of using sieves
	excel_blaze: 2018-05-21 16:07:54 simple logic and implementation(^_^) nice for beginners Last edit: 2018-05-21 16:08:46
	nadstratosfer: 2018-03-21 19:09:52 Took me 7+ hours in 3 sittings to fit within this retarded TL in PyPy. Props to julkas for showing it's possible. Edit: Thanks to psetter or admins for sensible TL correction. Last edit: 2020-12-22 22:19:37
	anupamwadhwa: 2018-02-07 19:30:21 Try NTG after this one.
	include_sajal: 2018-01-13 18:13:41 Using Euler Phi will bring extra overheads. Try something different. Though one can apply Euler Phi cautiously to get AC. BTW, an awesome one!
	chetan4060: 2018-01-01 11:00:39 very good concept mobius function. Last edit: 2018-04-16 21:05:26
	vib_s02: 2017-09-02 15:12:56 How does one find all divisors of N multiple times?
	hacker_sk: 2016-09-25 15:54:50 AC in one go :D.. 0.27 sec Really nice problem.. it will clear all the concepts related to gcd and totient. Last edit: 2016-09-30 20:01:11
	mkfeuhrer: 2016-08-15 11:23:29 euler phi :-)