[TJOI2010] 分金币

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

2
3
2 2 4
4
1 2 3 6

输出样例 #1

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}$。