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


avx_5801:
20210611 20:40:54
I'm a faggot Last edit: 20210612 09:27:38 

anikett:
20210322 11:41:51
Don't solve in python :/ , AC in C++ 

mahbubsabuj:
20210320 17:33:45
do not comment useless comment like ac in one go. 

anisf:
20201009 12:14:07
Accept in One GO!!!!!!!


fetus:
20200708 09:09:38
I ripped a formula from somewhere so now I can pretend to be a problem solver. Last edit: 20210612 09:29:06 

priyankarai:
20200611 19:37:31
how to get rid of TLE. my time complexity is O(n log n +t*sqrt(n) ) 

abuhuraira071:
20200423 20:34:22
lcm(factor of n,n)=n; 

zakir_1999:
20200203 19:59:52
I got Tl useing sieve function.what can I do at now??

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 