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

Bhavik:
20140216 19:20:51
learnt something new..:) Last edit: 20140216 19:21:14 

adhikari vushesh babu:
20130920 20:53:58
At last green light :)


Ouditchya Sinha:
20130429 08:40:16
Great Problem! Learnt a lot about totient function... But I think there's some server instability, my earlier solution ran in 4.19s on ideone & here it TLE'd, my improved solution ran in 0.42s on ideone & here it took 4.13s. Strange. :) 

Rajarshi Sarkar:
20130429 06:55:43
One does not simply calculate LCM :D 

saket diwakar:
20130130 23:14:57
finally got AC....:)


Benjamin Pinaya:
20120221 04:17:08
One does not simply uses Java in Spoj <Boromir> :D 

David:
20111223 04:11:57
Not enough time or too many test cases for Java. Precompute sum for all n from 1 to 1000000 and store results in array. Elapsed time for this effort is 0.250 sec.

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 