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
subhaammmm: 2024-07-12 18:18:14

Euler's totient function. but we wont precompute the result like seive. as it will give a TLE

pnm03: 2023-12-09 10:55:06

Ans wrong. Thử nghiệm vẫn đúng ???

Last edit: 2023-12-09 10:55:31
berlin03spoj: 2023-07-27 12:16:59

If you faced TLE, read about LcmSum formula , it using ETF to caculate

under_rated: 2023-06-20 07:24:40

everyone talk about TLE , but you will waste hours if don't know the formula

Last edit: 2023-06-20 07:33:29
nitin12384: 2023-02-05 10:21:52

Does this problem has anything to do with Mobius Inversion ?

rouge_kitty: 2022-08-29 18:41:11

you can check out my method here if you are getting a TLE and cannot figure out why: <snip>
[Simes]: No thanks, we don't want links to solutions.

Last edit: 2022-08-29 19:53:39
tadros: 2022-06-06 23:53:28

how could you solve this problem guys?

minhnguyent546: 2022-03-27 11:55:04

Just avoid t * sqrt(n)
I'm using generate all factor from prime factor and i get AC. Hope you guys get it

lakshya_1412: 2021-10-21 13:01:05

WA in ALL GO's

Vladimir Kirichenkoff: 2021-07-30 02:22:35

To solve this task perform next steps:
1. Fast factor base generation.
2. Find recurrent formula.


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