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

 < Previous 1 2 3 4 Next > anisf: 2020-10-09 12:14:07 Accept in One GO!!!!!!! fetus: 2020-07-08 09:09:38 ∑LCM(i, n) = ((∑(d * ETF(d)) + 1) * n) / 2 where ETF(d) is Euler totient function of d and d belongs to the set of divisors of n. try to use this formula... source--geeksforgeeks 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) 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??