Busy Beaver 在一个坑里装了 $N$ 个带有标号的橘子。第 $i$ 个橘子的标号为 $a_i$。

Busy Beaver 正在用这些橘子玩一个游戏。初始分数为 0。然后，直到只剩下一个橘子为止，Busy Beaver 会选择两个橘子 $i$ 和 $j$，获得 $|a_i - a_j|$ 分，丢弃其中一个橘子，并将另一个放回坑里。

求 Busy Beaver 能获得的最大分数。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^4$) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 2 \cdot 10^5$)。

每个测试用例的第二行包含 $N$ 个整数 $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$)。

所有测试用例中 $N$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 Busy Beaver 能获得的最大分数。

样例

输入样例 1

3
3
1 6 3
1
4
5
1 500000000 500000000 500000000 1000000000

输出样例 1

8
0
2499999999

说明

对于第一个测试用例，Busy Beaver 应该首先选择橘子 2 和 3，获得 $|6 - 3| = 3$ 分，然后丢弃橘子 3。接着，选择橘子 1 和 2，Busy Beaver 获得额外的 $|1 - 6| = 5$ 分，最终总分为 8 分。这是 Busy Beaver 能获得的最大分数。