Ali has a little annoying young brother called Adam, to get rid of him he decided to develop a game for him.
The game is as follow, there is a grid of size $n*n$,the cells of the grid contains coins as its order in the grid starting from the top left cell $(1,2,3 \dots n*n)$. In other words, $a_{ij}$ contains $(i-1) \cdot n+j$ coins such that $(1 \le i, j \le n)$.
The goal of the game is to calculate the maximum number of coins that can be collected from the grid, where Adam can collect the coins from any cell he wants (from any number of cells), such that no two cells are on the same row or column.
As Adam is so young he asked you to help him. so would you?
The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \le t \le 10^5)$ --- the number of test cases.
The first line of each test case contains only one integer $n$ $(1 \le n \le 10^6)$ --- the size of the grid.
For each test case print only one integer, the maximum number of coins Adam can collect.
| Input | Output |
|---|---|
5 1 2 3 4 5 Copy
|
1 5 15 34 65 Copy
|
Let's redraw the grid after adding an extra row and an extra column in this way :
Let $n = 4$ without loss of generality :
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 |
| 4 | 5 | 6 | 7 | 8 |
| 8 | 9 | 10 | 11 | 12 |
| 12 | 13 | 14 | 15 | 16 |
We can observe that the value in each cell is the sum of the two new values added in its row and column.
Since we are choosing $n$ cells with distinct rows and columns, then we will be adding the values from the extra row and the extra column (the ones we added in the above) at most once each.
So, if we choose any $n$ cells in this way, we will always get the sum of values $(1 \rightarrow n)$ + the sum of values $n * (1 \rightarrow (n - 1))$
Which is equal to:
$n*(n+1)/2 + n*(n*(n-1)/2)$
$n$ could go up to $10^6$ which makes the result fit inside a long long integer for C++ (64 bit integer).