## 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 > Vladimir Kirichenkoff: 2021-07-30 02:22:35 To solve this task perform next steps: 1. Fast factor base generation. 2. Find recurrent formula. 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. avx_5801: 2021-06-11 20:40:54 I'm a faggot Last edit: 2021-06-12 09:27:38 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??