题目背景

题目描述

你是一位国王。

你有 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

你每次可以将一个整数加一，但要花费一块钱。

你希望花一些钱让这 $n$ 个整数的异或和为 $0$。

你不希望浪费钱财，你希望知道最少要花多少钱。

输入格式

第一行一个整数 $T$，表示数据组数。

每组数据的第一行为一个整数 $n$。

每组数据的第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

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

样例一

input

4
3
3 4 5
4
5 3 0 7
3
2 3 1
5
7 7 7 7 7

output

2
1
0
9

样例二

见下发文件中的 king/ex_king2.in 以及 king/ex_king2.ans。

样例三

见下发文件中的 king/ex_king3.in 以及 king/ex_king3.ans。

限制与约定

对于 $100\%$ 的数据，$1\le T\le 100$，$2\le n,\sum n\le 10^6$，$0\le a_i<2^{60}$。