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

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

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

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

每组测试数据占两行。

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

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

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

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