LCMSUM - LCM Sum


Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.

Input

The first line contains T the number of test cases. Each of the next T lines contain an integer n.

Output

Output T lines, one for each test case, containing the required sum.

Example

Sample Input:
3
1
2
5

Sample Output:
1
4
55

Constraints

1 <= T <= 300000
1 <= n <= 1000000


hide comments
rohit9934: 2017-06-30 13:09:54

I have got so many TLE's in this
Some points before attempting.
prefer Pre-computation guys otherwise TLE
GCD will not work even the straight forward formula
Don't use endl in c++ use "\n" otherwise TLE
Dont use cin cout , use printf, scanf otherwise TLE.
Must do ,you will learn a lot.

Last edit: 2017-06-30 13:10:30
da_201501181: 2017-04-02 13:54:53

Learned a lot..!! Nice Question..!!

rohan_c_23: 2016-10-13 13:33:03

Wonderful mathematics!!

square1001: 2016-07-23 13:36:06

I suggest this problem: LCM Rush(Japanese).
But problem statement is simple.
You're given N and K. Calculate LCM(1,K) + LCM(2,K) + LCM(3,K) + ... + LCM(N,K).
http://abc020.contest.atcoder.jp/tasks/abc020_d#

vaibhav goyal: 2016-07-08 16:59:03

scanf is also giving tle's
finally got ac by fast i/o
nice problem :)

ritik_agr: 2016-07-04 05:39:57

learnt new concepts from this problem

Last edit: 2016-07-04 05:40:16
sanghpriya785: 2015-10-06 13:41:37

getting tle in c as well as in python also.
but learn a lot

Infinity: 2014-11-03 12:02:03

interesting problem.Had to refer the web to get the first idea.

Last edit: 2014-11-03 13:05:20
pankaj: 2014-10-23 08:50:15

final AC

Bhavik: 2014-02-16 19:20:51

learnt something new..:)

Last edit: 2014-02-16 19:21:14

Added by:Varun Jalan
Date:2010-01-24
Time limit:0.527s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6
Resource:own problem used for Codechef Snackdown Onsite