题目内容

调度模块要把 $n$ 个工单均分到两个班次（$n$ 为偶数）。第 $i$ 个工单的收益为 $v_i$。每一班恰好分到 $\frac{n}{2}$ 个工单；值班侧会先挑走总收益更高的那一班。两边都会按对自己最有利的方式决策。

请计算：在双方都足够聪明的前提下，两班总收益之差的最小可能值。两班收益分别为 $S$ 与 $V-S$，其中

差值定义为 $\lvert 2S-V\rvert$。

输入描述

第一行一个整数 $q$（$1 \le q \le 80$），表示随后询问个数。接下来对每个询问：

• 第一行读入一个偶数 $n$（$2 \le n \le 30$），表示工单数量。
• 第二行读入 $n$ 个整型 $v_1,v_2,\dots,v_n$（$1 \le v_i \le 1000000000$），表示各工单收益。

对每个询问逐一计算。

输出描述

对每个询问写出一行一个非负整数，表示两班总收益差的最小可能值。

样例1

输入

2
2
4 9
4
3 5 6 8

输出

5
0

说明

第一个询问只有一种均分：$\{4\}$ 与 $\{9\}$，差为 $5$。第二个询问取 $\{3,8\}$ 与 $\{5,6\}$，两班和都是 $11$，差为 $0$。

样例2

输入

2
4
1 2 3 6
6
1 2 3 4 5 6

输出

2
1

说明

$n=4$ 时，$\{1,6\}$ 与 $\{2,3\}$ 的和为 $7$ 与 $5$，差 $2$，已是最小。$n=6$ 时，例如 $\{1,4,6\}$ 与 $\{2,3,5\}$ 的和为 $11$ 与 $10$，差 $1$。