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 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
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 :-)

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.


Added by:Phenomenal
Date:2009-02-16
Time limit:0.237s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM World Final Warm up 1 - 2008