Background

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

Problem Description

Given $n$, compute

where $\operatorname{lcm}(i, j)$ denotes the least common multiple of $i$ and $j$.

Input Format

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$.

Output Format

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

3
1
2
5

1
4
55

Hint

• 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