Professor Zhang 有 $n$ 种字符，第 $i$ 种字符的数量为 $a_i$。Professor Zhang 想要使用所有的字符构建若干个回文串，并希望最大化这些回文串中长度最短的那一个的长度。

例如，假设有 4 种字符，分别记为 ‘a’, ‘b’, ‘c’, ‘d’，它们的数量分别为 $\{2, 3, 2, 2\}$。Professor Zhang 可以构建 (“acdbbbdca”)，或者 (“abbba” 和 “cddc”)，或者 (“aca”, “bbb” 和 “dcd”)，或者 (“acdbdca” 和 “bb”)。第一种方案是最优解，其中最短回文串的长度为 9。

注意，如果一个字符串从左向右读和从右向左读是一样的，则称其为回文串。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)：字符的种类数。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^4$)。

测试数据最多有 110 组，输入文件总大小不超过 6 MB。

输出格式

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

样例

输入格式 1

4
4
1 1 2 4
3
2 2 2
5
1 1 1 1 1
5
1 1 2 2 3

输出格式 1

3
6
1
3