题目描述

为了劳逸结合，我们敬爱的牛老师准备了一场拔河比赛，让队员放松心情。

为了拔河比赛的公正性，牛老师提出以下要求：
$(1)$ 拔河比赛两边人数最多不能相差 $1$。
$(2)$ 每个队员都有体重，我们要使两边比赛的人体重和相差最小。

现在有 $N$ 个队员，牛老师想你帮忙分配，并且把分配后两边体重和之差最小值输出。

输入格式

首先输入 $T$，表示有 $T$ 组样例。

每个样例：

首先输入人数 $N$，占一行。

后面跟着 $N$ 个数，表示 $N$ 个人的体重 $W_1 - W_n$。

输出格式

对于每个样例输出一行，一个整数表示两边体重之差的绝对值。

样例

1
3
55 50 100

样例输出

5

限制与提示

对于 $100\%$ 的数据，有 $1 \leq T \leq 50$，$2 \leq N \leq 20$，$30 \leq W_i \leq 120$。

时间限制：1000 ms

空间限制：256 MiB