8145 巧分配

题目信息

• 时间限制: 1秒
• 内存限制: 128MB

题目描述

D组在拔河。同学们不同意按人数平分，而是希望按体重平分成两组。根据小组人员的实际体重（自创计量单位），设计分配方案，使两组体重和的差距最小（两组人数可以不同）。

注意：本题有多组测试。

输入格式

第一行为测试数据组数 T。

针对每组测试数据：

• 第一行，一个正整数 n，表示小组总人数
• 第二行，n 个正整数，中间用空格隔开，表示每个同学的体重

输出格式

每组测试数据输出一行： 一个非负整数，表示两组体重和的最小差距。

数据范围

• 0 < T < 6
• 1 < n < 1000
• 所有人员体重和 ≤ 100000

样例

样例 1

输入

1
9
6 3 1 2 4 8 7 8 9

输出

0