安德烈刚刚开始遇到问题,这对他来说很困难。这就是为什么他提出了一个关于排列$$$^{\dagger}$$$的奇怪问题并要求你解决它。你能做到吗?
我们将长度为 $$$n$$$ 的排列 $$$p$$$ 的成本称为表达式的值:
$$$(\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)$$$。
找出长度为 $$$n$$$ 的所有排列中的最大成本。
$$$^{\dagger}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 30$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 250$$$) — 排列的长度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$。
输出
对于每个测试用例,输出一个整数 — 所有长度为 $$$n$$$ 的排列中的最大成本。
示例
输入 #1
5 2 4 3 10 20
输出 #1
2 17 7 303 2529
注意
在第一个测试用例中,成本最大的排列是 $$$[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$$$。