No testdata at current.

题目描述

在浙江师范大学 ACM 集训队，队员平时集训脑力劳动力比较重。为了劳逸结合，我们敬爱的韩老师准备了一场拔河比赛，让队员放松心情。

为了拔河比赛的公正性，韩老师提出以下要求：

1. 拔河比赛两边人数最多不能相差 $1$。
2. 每个队员都有体重，我们要使两边比赛的人体重和相差最小。

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

输入格式

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

每个样例：

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

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

输出格式

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

样例

样例输入

1
3
55 50 100

样例输出

5

数据范围与提示

对于 $100\%$ 的数据，有 $1\le T\le50$，$n\le N\le20$，$30\le W_i\le120$。