Description

Still in the familiar place: there are a total of $n$ window ledges, numbered from top to bottom, with the topmost being numbered $1$ and the bottommost being numbered $n$. Tianyi notices that the snow accumulations on each ledge can be viewed as a multiset of snowballs, where initially, the first ledge holds a single snowball with a volume of $1$, while the other ledges are devoid of any snow. Suddenly, a gust of wind laden with snow blows through, instigating $n$ transformations in the snow accumulations -

In the $i$-th transformation, every snowball on the $i$-th ledge is lifted up. Due to peculiar physical phenomena, all ledges whose numbers are multiples of $i$ (excluding $i$ itself) receive new snow accumulations. Specifically, let the volume of a lifted snowball be $V$. Among these receiving ledges, the one with the largest number receives a snowball of volume $V+1$, the second largest receives a snowball of volume $V+2$, and so on. In the end, the lifted snowball mysteriously returns to the $i$-th ledge, leaving the snow accumulation on the $i$-th ledge unchanged after this transformation.

Ling knows that Tianyi is intrigued by the question: After the $n$ transformations, what is the total volume of the largest snowball on each ledge? As they sit peacefully admiring the snow, you are tasked with answering this question for them.

Input Format

The first line of the input contains an integer $T$ — the number of test cases.

The only line of each test case contains an intergers $n$ — the number of window ledges.

Output Format

For each test case, output a single integer — the total volume of the largest snowball on each ledge.

5
1
5
3
114514
2000000

1
18
6
18057023450
5575638612615

Hint

Sample Explanation

The final state when $n=5$ is as follows:

On the first ledge is a snowball with a volume of $1$;
On the second ledge is a snowball with a volume of $5$;
On the third ledge is a snowball with a volume of $4$;
On the fourth ledge are two snowballs with volumes of $3,6$;
On the fifth ledge is a snowball with a volume of $2$;

The total volume of the largest snowball on each ledge is $1+5+4+6+2=18$.

Constrains

Subtasks applied. You can only gain the score of the subtask if you accepted all the tests in the subtask.

For all tests, it is guaranteed that $1\le T\le5\times10^5$，$1\le n\le2\times10^6$.