CF1859C.Another Permutation Problem

Andrey is just starting to come up with problems, and it's difficult for him. That's why he came up with a strange problem about permutations$^{\dagger}$ and asks you to solve it. Can you do it?

Let's call the cost of a permutation $p$ of length $n$ the value of the expression:

$(\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)$.

Find the maximum cost among all permutations of length $n$.

$^{\dagger}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

安德烈刚开始尝试出题，但这对他来说十分困难。因此，他想出了一个关于排列$^{\dagger}$ 的奇怪问题，并请你来解答。你能解决它吗？

我们定义长度为 $n$ 的排列 $p$ 的代价为如下表达式的值：

$$\left(\sum_{i = 1}^{n} p_i \cdot i\right) - \left(\max_{j = 1}^{n} p_j \cdot j\right).$$

请找出所有长度为 $n$ 的排列中，代价的最大值。

$^{\dagger}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 这 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 30$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer $n$ ($2 \le n \le 250$) — the length of the permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 30$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$2 \le n \le 250$），表示排列的长度。

保证所有测试用例的 $n$ 值之和不超过 $500$。

For each test case, output a single integer — the maximum cost among all permutations of length $n$.

对于每个测试用例，输出一个整数——所有长度为 $n$ 的排列中的最大代价。

In the first test case, the permutation with the maximum cost is $[2, 1]$. The cost is equal to $2 \cdot 1 + 1 \cdot 2 - \max (2 \cdot 1, 1 \cdot 2)= 2 + 2 - 2 = 2$.

In the second test case, the permutation with the maximum cost is $[1, 2, 4, 3]$. The cost is equal to $1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4 - 4 \cdot 3 = 17$.

在第一个测试用例中，成本最大的排列是 $[2, 1]$。其成本等于 $2 \cdot 1 + 1 \cdot 2 - \max (2 \cdot 1, 1 \cdot 2)= 2 + 2 - 2 = 2$。

在第二个测试用例中，成本最大的排列是 $[1, 2, 4, 3]$。其成本等于 $1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3 + 3 \cdot 4 - 4 \cdot 3 = 17$。