[TJOI2010] 分金币

现在有 $n$ 枚金币，它们可能会有不同的价值，第 $i$ 枚金币的价值为 $v_i$。 现在要把它们分成两部分，要求这两部分金币数目之差不超过 $1$，问这样分成的两部分金币的价值之差最小是多少？

**本题单个测试点内有多组测试数据**。 输入的第一行是一个正整数 $T$，表示该测试点内数据组数。 对于每组测试数据的格式为： 每组测试数据占两行。 第一行是一个整数 $n$，表示金币的个数。 第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个金币的价值 $v_i$。

对于每组数据输出一行一个整数表示答案。

2
3
2 2 4
4
1 2 3 6

0
2

#### 数据规模与约定 - 对 $30\%$ 的数据，保证 $1 \leq v_i \leq 1000$ - 对于 $100\%$ 的数据，保证 $1 \leq T \leq 20$，$1 \leq n \leq 30$，$1 \leq v_i \leq 2^{30}$。