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
Ouditchya Sinha: 2013-04-29 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: 2013-04-29 06:55:43

One does not simply calculate LCM :D

saket diwakar: 2013-01-30 23:14:57

finally got AC....:)
same algo getting TLE in python..#strange

Last edit: 2013-01-30 23:16:40
Benjamin Pinaya: 2012-02-21 04:17:08

One does not simply uses Java in Spoj <Boromir> :D

David: 2011-12-23 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.

Still get TLE. Java I/O too slow. Sigh.

Last edit: 2011-12-23 04:12:37

Added by:Varun Jalan
Date:2010-01-24
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