题目描述

你有一个长度为 $n$ 的数组 $a$，你将用 $a$ 按以下方式构造两个数组 $b$ 和 $c$，两个数组都包含 $n$ 个元素：

• $b_i=\min(a_1,a_2,\ldots,a_i)$
• $c_i=\max(a_1,a_2,\ldots,a_i)$

定义 $a$ 的得分为 $\sum_{i=1}^nc_i-b_i$（即对所有 $c_i-b_i$ 进行求和）。在计算得分之前，您可以随意重新排列 $a$。

找出对 $a$ 进行重新排列可以得到的最高得分。

输入输出格式

输入格式

第一行包含 $t(1\le t\le 100)$——测试用例数。

每个测试用例的第一行包含一个整数 $n(1\le n\le 1000)$——$a$ 中元素的个数。

下面一行包含 $n$ 个整数 $a_1,a_2,...,a_n(1\le a_i\le 1000)$——数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 1000。

输出格式

对于每个测试用例，输出所能得到的最高得分。

样例

3
1
69
3
7 6 5
5
1 1 1 2 2

0
4
4

提示

在第一个测试案例中，没有其他方法可以重新排列 $a$。因此，$b=[69], c=[69]$。唯一可能的得分是 $69-69=0$。

在第二个测试案例中，可以将 $a$ 重排为 $[7,5,6]$。这里，$b=[7,5,5], c=[7,7,7]$。这种情况下的得分是 $(7-7)+(7-5)+(7-5)=4$。可以看出，这是可能的最高得分。

对于 $10\%$ 的测试数据，$n\le 5$；

对于 $20\%$ 的测试数据，$n\le 25$；

对于 $100\%$ 的测试数据，$n\le 1000$。