C. 明日奈与蚊子
每个测试点时间限制：2 秒
内存限制：256 兆字节

生日那天，明日奈的 $n$ 位仰慕者每人送了她一座塔。第 $i$ 位仰慕者送的塔的高度为 $a_i$。

明日奈评价收到礼物美丽程度的方式是 $\max(a_1, a_2, \dots, a_n)$。她可以进行以下操作任意次（可能为零次）：

选择满足 $1 \le i \neq j \le n$ 且 $a_i + a_j$ 为奇数且 $a_i > 0$ 的 $(i, j)$，然后将 $a_i$ 减少 $1$，将 $a_j$ 增加 $1$。

容易看出，在操作过程中塔的高度始终保持非负。

请帮助明日奈求出经过任意次操作后，礼物美丽程度的最大可能值。

输入格式

每个测试文件包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。每个测试用例的描述如下：

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示明日奈的仰慕者人数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示塔的高度。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数：明日奈能够达到的美丽程度的最大可能值。

示例输入

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

示例输出

9
5
5
21

提示

• 在第一个测试用例中，没有一对塔满足进行操作的所需条件，因此不能执行任何操作。此时答案为 $\max(5, 3, 9) = 9$。
• 在第二个测试用例中，可以对 $(i=2, j=1)$ 应用两次操作。之后数组变为 $[5, 0]$，因此答案为 $5$。
• 在第三个测试用例中，可以执行以下操作序列：
  • 对 $(i=1, j=2)$ 操作：$[1, 2, 2, 1] \to [0, 3, 2, 1]$
  • 对 $(i=3, j=2)$ 操作：$[0, 3, 2, 1] \to [0, 4, 1, 1]$
  • 对 $(i=3, j=2)$ 操作：$[0, 4, 1, 1] \to [0, 5, 0, 1]$
    $\max(0, 5, 0, 1) = 5$，因此答案为 $5$。