P1891 Crazy LCM

As we all know, czmppppp is a math genius. One day, he gave the newbies a number theory problem, and they were all shocked.

Given $n$, compute $$\sum_{i = 1}^n \operatorname{lcm}(i, n)$$ where $\operatorname{lcm}(i, j)$ denotes the least common multiple of $i$ and $j$.

**There are multiple test cases in a single test point.** The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain one integer $n$.

For each test case, output one line with a single integer representing the answer.

- Constraints: - For $30\%$ of the testdata, $T \leq 5$, $n \leq 10^5$. - For $100\%$ of the testdata, $1 \leq T \leq 3 \times 10^5$, $1 \leq n \leq 10^6$. Translated by ChatGPT 5