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
shammya:
20191123 17:21:06
1.use printf scanf for I/O to avoid TLE


kamesh11:
20190910 15:41:34
Very nice problem. Took me almost 45 hours to eliminate that TLE...huh! 

sid779:
20190701 19:17:11
AC in one go but I looked for the proof on google as I can't think of a solution :( 

whyamievenhere:
20181220 17:28:09
Again man useless time limits, how the heck are we supposed to find divisors of a number range without sieve?? 

DK...:
20180830 18:43:29
i got TL using pragma's, but AC without them...


uvshuvo:
20180629 01:30:42
Learned a lot about phi function nice math logic Thanks. Last edit: 20180629 01:34:23 

crackeree:
20180503 14:49:26
how alien i m. everyone is getting TLE .. and i m getting WA..


chetan4060:
20180101 09:51:18
nice math used:) 

epsilonalpha:
20171214 07:37:25
It's a must do NT problem.


shub120798:
20170927 08:51:33
really nice prblm.. precompute each and every thing to avoid tle;..

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