有 $n$ 堆砖块，第 $i$ 堆包含 $a_i$ 块砖。

现在，你和你的对手轮流进行操作，你的对手先手。每次操作，玩家可以选择一堆砖块并移走其中的若干块砖。无法进行操作的玩家输掉游戏。

在游戏开始之前，你可以选择移除或添加一些砖块。你允许完全移除一堆砖块，但不能创建新的砖堆。每移除或添加一块砖，你将消耗 1 点能量。求你赢得游戏所需的最小能量。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。

接下来有 $2 * T$ 行。每相邻两行描述一个测试用例。

每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示砖堆的数量。

每个测试用例的第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示每堆砖块的数量。

输出格式

对于每个测试用例，在一行中输出一个整数，表示赢得游戏所需的最小能量。

样例

输入样例 1

4
2
1 7
3
1 1 1
4
1 2 5 20
5
1 15 20 35 100

输出样例 1

6
1
12
37