题目描述

在丛林探险的时候，你遇到了一只罕见的戴着领结的猩猩！你和猩猩握了握手并给了它一些食物和水。作为回报……

猩猩给了你一个长度为 $n$ 的数组 $a$。通过数组 $a$ 你将会以下列的方式构造两个长度都为 $n$ 的数组 $b$ 和 $c$：

• $b_i = \text{min}(a_1,a_2,…,a_i),1 \le i \le n$。
• $c_i = \text{max}(a_1,a_2,…,a_i),1 \le i \le n$。

定义 $a$ 的得分为 $\sum^n_{i=1} c_i-b_i$。在你计算分数之前，你可以任意修改 $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$。

输出格式

对于每组数据，输出一行一个整数，表示可以获得的最高得分。

说明/提示

对于第一组数据，没有其他方法来重新排列 $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$。可以证明，这是可能的最高分数。

翻译来自 Jason_Ming。

样例

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

0
4
4