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
sankalp_7: 2021-06-27 17:13:18

If you are doing this question in O(n log n +t*sqrt(n) ) (TLE will come)
Means you know the concept.
Just to avoid sqrt(n) pre-compute answer just like sieve concept.

anikett: 2021-03-22 11:41:51

Don't solve in python :/ , AC in C++

mahbubsabuj: 2021-03-20 17:33:45

do not comment useless comment like ac in one go.

anisf: 2020-10-09 12:14:07

Accept in One GO!!!!!!!

fetus: 2020-07-08 09:09:38

I ripped a formula from somewhere so now I can pretend to be a problem solver.

Last edit: 2021-06-12 09:29:06
priyankarai: 2020-06-11 19:37:31

how to get rid of TLE. my time complexity is O(n log n +t*sqrt(n) )

abuhuraira071: 2020-04-23 20:34:22

lcm(factor of n,n)=n;

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)


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