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
zakir_1999: 2020-02-03 19:59:52

I got Tl useing sieve function.what can I do at now??

alexardelean: 2020-01-12 15:49:47

Ac in one go. Found the problem by seeing the solution lmao

shammya: 2019-11-23 17:21:06

1.use printf scanf for I/O to avoid TLE
2.Learn the formula to calculate LCM sum.
3.use sieve to calculate phi() in O(nlogn) time
4.using the formula pre-calculate ans in O(nlogn) time
Total complexity = O(nlogn)

kamesh11: 2019-09-10 15:41:34

Very nice problem. Took me almost 4-5 hours to eliminate that TLE...huh!

sid779: 2019-07-01 19:17:11

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

whyamievenhere: 2018-12-20 17:28:09

Again man useless time limits, how the heck are we supposed to find divisors of a number range without sieve??

DK...: 2018-08-30 18:43:29

i got TL using pragma's, but AC without them...

uvshuvo: 2018-06-29 01:30:42

Learned a lot about phi function nice math logic Thanks.

Last edit: 2018-06-29 01:34:23
crackeree: 2018-05-03 14:49:26

how alien i m. everyone is getting TLE .. and i m getting WA..

chetan4060: 2018-01-01 09:51:18

nice math used:)


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