显生之宙

题号：NC267923
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

众数归于本初
生命就此苏生

白垩色的王子给了你一个由 $n$ 个数组成的数列，并告诉你，你需要执行 $n-1$ 次如下操作：
选定一个数列中的数 $x$ ，再选择数列中的至少一个其他数，然后让这些数都加上 $x$ ，再将 $x$ 移除出这个数列。
经 $n-1$ 次操作过后，数列中最后只会剩下一个数。白垩色的王子希望你告诉他，最后剩下的那个数最小是多少。题目保证最后输出的答案的绝对值 $\le 4\times 10^{18}$ 。

输入描述:

第一行输入一个整数 ，表示数据组数。
对于每一组数据，第一行输入一个整数 ，表示初始数列中有  个数。
接下来一行，输入  个数 ，表示初始数列。

输出描述:

对于每一组数据，输出一行一个整数，表示最后剩下的那个数的最小值。

示例1

输入

复制

输出

复制

3
-2

说明

对于第一组数据：一种方案是令  加上 ，结果为 。
对于第二组数据：一种方案是先令其他三个数各加上 ，数列变为 ，再令其他两个数各加上 ，数列变为 ，最后令  加上 ，结果为 。

示例2

输入

复制

1
6
-1 -2 -3 100 200 300

输出

复制

说明

一种方案是先令其他五个数各加上 ，数列变为 ，再令其他四个数各加上 ，数列变为 ，再令其他三个数各加上 ，数列变为 ，然后三个数依次加给下一个数，得到答案。