[TJOI2010]分金币

题目描述

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

输入输出格式

输入格式


每个输入文件中包含多组测试数据,输入文件的第一行是一个正整数T,用来说明文件中有多少组测试数据。接下来将依次给出所有测试数据的描述,每组测试数据的第一行是一个正整数n,表示共有n枚金币。第二行有n个正整数vi,分别给出每一枚金币的价值。

输出格式


对每一组输入数据,输出一个非负整数,表示分成的两部分金币的价值差别的最小值。

输入输出样例

输入样例 #1

2
3
2 2 4
4
1 2 3 6

输出样例 #1

0
2

说明

对30%的数据,1 ≤ vi ≤ 1000 对100%的数据,1 ≤ n ≤ 30,1 ≤ vi ≤ 2^30,T ≤ 20 每个测试点时限1秒 注意:对于使用C/C++语言的选手,若需使用64位整型数,应声明为long long,若需使用scanf()/printf()/fscanf()/fprintf()等系列函数,应配合使用"%lld"标记符进行long long类型的输入输出。