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
shub120798:
20170927 08:51:33
really nice prblm.. precompute each and every thing to avoid tle;..


rohit9934:
20170630 13:09:54
I have got so many TLE's in this


da_201501181:
20170402 13:54:53
Learned a lot..!! Nice Question..!! 

rohan_c_23:
20161013 13:33:03
Wonderful mathematics!!


square1001:
20160723 13:36:06
I suggest this problem: LCM Rush(Japanese).


vaibhav goyal:
20160708 16:59:03
scanf is also giving tle's


ritik_agr:
20160704 05:39:57
learnt new concepts from this problem Last edit: 20160704 05:40:16 

sanghpriya785:
20151006 13:41:37
getting tle in c as well as in python also.


Infinity:
20141103 12:02:03
interesting problem.Had to refer the web to get the first idea. Last edit: 20141103 13:05:20 

pankaj:
20141023 08:50:15
final AC 
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 