题目描述

Eralim（原文人名）作为 mafia（原文组织名）老大，管理着 $n$ 名战士。第 $i$ 名战士的评分为 $a_i$。

Eralim 安排了一场 $n-1$ 场战斗的锦标赛，每场战斗中都会选择两名尚未被淘汰的战士 $i$ 和 $j$（其中 $1 \le i < j \le n$），而战斗的结果是战士 $i$ 被淘汰出比赛，战士 $j$ 的评分会减去战士 $i$ 的评分相同。也就是说，$a_j$ 会减去 $a_i$。请注意，战士 $j$ 的评分可能会变为负数。战士们的编号不会改变。

Eralim 想知道，如果他最优地选择战斗，最后剩下的那名战士最多能保持多少评分。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——战士的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots a_n$（$1 \le a_i \le 10^9$）——战士的评分。

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

输出格式

对于每个测试用例，输出一个整数——最后一个剩余战士可以保持的最高评分。

说明/提示

在第一个例子中，你可以安排编号为 $1$ 和 $2$ 的战士之间的比赛，其中编号为 $2$ 的战士会获胜。最后一个战士的评分，即编号为 $2$ 的战士，将是 $1-2=-1$。

在第二个例子中，你可以先让编号为 $1$ 和 $2$ 的战士进行比赛，其中编号为 $2$ 的战士会获胜，然后让编号为 $2$ 和 $3$ 的战士进行比赛，其中编号为 $3$ 的战士会获胜。

在第一场比赛后，编号为 $2$ 的战士的评分将是 $2-2=0$。在第二场比赛后，编号为 $3$ 的战士的评分将是 $8-0=8$。

翻译者：jiangyunuo。

样例

5
2
2 1
3
2 2 8
4
1 2 4 3
5
1 2 3 4 5
5
3 2 4 5 4

-1
8
2
7
8