题目描述

你有有 $n$ 枚货币,每个货币可能会有不同的价值,第 $i$ 个货币的价值为 $v_i$ 。

现在要把所有给定的货币分成两部分,要求这两份货币数目之差不超过 1,问这样分成的两份货币的价值之差最小是多少?


输入格式

本题单个测试点内有多组测试数据。

输入的第一行是一个正整数 T,表示该测试点内数据组数。

每组测试数据占两行。

第一行是一个整数 n,表示货币的个数。

第二行有 n 个整数,第 i 个整数表示第 i 个货币的价值 $v_i$。


输出格式

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


样例数据

输入

2
3
3 3 6
4
1 2 3 6

输出

0
2

备注

$1 \leq T \leq 20,1 \leq n \leq 30,1 \leq v_i \leq 2^{30}$
本题大家可以使用模拟退火来做。


信息

时间限制: 4s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务