题目描述

Jack 和 John 继承了一笔遗产，这笔遗产包括了 \(n\) 件财物（有地产、存款、股票等），每件财物的价值分别为 \(a_i\)，现在他们要平分这笔遗产，但又不能把单件财物分割开来。请你为他们分配一下财物，使得他们两人所得到财物的价值差距最小。

格式

输入格式

第一行为正整数 \(t(≤10)\)，表示测试数据组数；每组数据中，第一行为正整数 \(n(≤50)\)，表示财物件数，第二行为 \(n\) 个以空格隔开的正整数 \(a_i(≤1000)\)，分别表示每件财物的价值。

输出格式

对于每组数据，输出平分遗产之后他们所得差距的最小值。

样例1

样例输入1

2
4
1 2 3 4
4 
1 2 5 10

样例输出1

0
2

样例解释

样例 \(1\) 中，可以把财物分为 \((1,4)\) 和 \((2,3)\)，差距为 \(0\)；

样例 \(2\) 中，可以把财物分为 \((1,2,5)\) 和 \((10)\)，差距为 \(2\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T3\)

文件IO

freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);