题目描述：

小度有一个数组，他每次操作可以选择两个不同的位置，其中一个作为 $i$ ，另一个作为 $j$ ，然后令 $ai=a_i +a_j$ ，但是对于每个位置，至多只能被选作 $i$ 一次（被选作 $j$ 的次数不限）。

小度想知道，他进行若干次操作后，数组最大的极差是多少。

格式

输入格式： 第一行输入一个整数 $T(1≤T≤10^5)$ 表示询问次数。 对于每次询问： 第一行输入一个整数 $n(1≤n≤10^5)$ 表示数组长度。 第二行输入 $n$ 个整数表示数组 $a(−10^9 ≤a_i​ ≤10^9 )$ 。 所有询问的数组总长度不超过 $2×10^5$ 。

输出格式：

输出一个整数表示答案。

样例 1

输入：

2
5
-2 -1 0 1 2
1
1

输出：

10
0

备注

第一次操作选择2，1，令：-1 + (-2) = -3

第二次操作选择1，2，令：-2 + (-3) = -5

第三次操作选择3，1，令：0 + (-5) = -5

第四次操作选择4，5，令：1 + 2 = 3

第五次操作选择5，4，令：2 + 3 = 5

此时数组变成：-5,-3,-5, 3, 5

极差为10。