题目描述

现在有 $n$ 枚金币，它们可能会有不同的价值，第 $i$ 枚金币的价值为 $v_i$。

现在要把它们分成两部分，要求这两部分金币数目之差不超过 $1$，问这样分成的两部分金币的价值之差最小是多少？

输入格式

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

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

对于每组测试数据的格式为：

每组测试数据占两行。

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

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

输出格式

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

2
3
2 2 4
4
1 2 3 6

0
2

提示

数据规模与约定

• 对 $30\%$ 的数据，保证 $1 \leq v_i \leq 1000$
• 对于 $100\%$ 的数据，保证 $1 \leq T \leq 20$，$1 \leq n \leq 30$，$1 \leq v_i \leq 2^{30}$。