回文序列

题目描述 你有�种字母，其中第�种字母出现次数为�� 。你想用这些字母拼成若干个串，要求 第�种字母恰好被用了�� 次，并且要求每个串都是回文串，使得其中最短的串长度 最大。

比如四种字符为’a’, ‘b’, ‘c’, ‘d’，出现次数分别为{2,3,2,2}，那么可能的其中几种方案 为 {“acdbbbdca”}, {“abbba”, “cddc”}, {“aca”, “bbb”, “dcd”}, 或{“acdbdca”, “bb”}。第 一种方案中，最短的串长度为 9，是最优的。

输入格式 多组数据，第一行一个整数�，表示数据组数。

对于每组数据，第一行一个整数�，接下来一行�个整数，表示每种字母出现的次 数。

输出格式 对于每组数据，输出一个数，表示答案。

样例输入 4 4 1 1 2 4 3 2 2 2 5 1 1 1 1 1 5 1 1 2 2 3

样例输出 3 6 1 3

数据规模 共 5 组数据。

测试点 1 满足� ≤ 4, �� ≤ 4。

测试点 2,3 满足，对于每组数据，� ≤ 1000, ∑�� ≤ 104 。

对于所有数据，满足 1 ≤ � ≤ 5 × 104 , 1 ≤ �� ≤ 104 , � ≤ 20。