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
pnm03:
20231209 10:55:06
Ans wrong. Thử nghiệm vẫn đúng ???


berlin03spoj:
20230727 12:16:59
If you faced TLE, read about LcmSum formula , it using ETF to caculate 

under_rated:
20230620 07:24:40
everyone talk about TLE , but you will waste hours if don't know the formula Last edit: 20230620 07:33:29 

nitin12384:
20230205 10:21:52
Does this problem has anything to do with Mobius Inversion ? 

rouge_kitty:
20220829 18:41:11
you can check out my method here if you are getting a TLE and cannot figure out why: <snip>


tadros:
20220606 23:53:28
how could you solve this problem guys?


minhnguyent546:
20220327 11:55:04
Just avoid t * sqrt(n)


lakshya_1412:
20211021 13:01:05
WA in ALL GO's 

Vladimir Kirichenkoff:
20210730 02:22:35
To solve this task perform next steps:


sankalp_7:
20210627 17:13:18
If you are doing this question in O(n log n +t*sqrt(n) ) (TLE will come)

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 