题目描述

在 小z 生日时，她的 $n$ 位仰慕者每人赠送了一座塔。第 $i$ 位仰慕者赠送的塔高度为 $a_i$。

小z 将礼物的美观度定义为 $\max(a_1, a_2, \ldots, a_n)$。她可以执行以下操作任意次数（包括零次）：

• 选择满足 $1 \leq i \neq j \leq n$ 的两个下标，使得 $a_i + a_j$ 为奇数且 $a_i > 0$。随后将 $a_i$ 减少 $1$，并将 $a_j$ 增加 $1$。

容易验证，在操作过程中塔的高度始终保持非负。请帮助 小z 求出经过任意次操作后可能达到的最大美观度。

输入格式

每个测试包含多个测试用例。输入数据第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) —— 测试用例数量。接下来是测试用例描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$) —— 小z 的仰慕者数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) —— 各塔的高度。

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

输出格式

对于每个测试用例，输出一个整数：小z 能获得的最大美观度。

输入输出样例 #1

输入 #1

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

输出 #1

9
5
5
21

说明/提示

第一个测试用例中，没有满足操作条件的塔对，因此无法进行任何操作。此时答案为 $\max(5, 3, 9) = 9$。

第二个测试用例中，可以对 $i=2$ 和 $j=1$ 执行两次操作。操作后数组变为：$a = [5, 0]$，因此答案为 5。

第三个测试用例中，可以执行以下操作序列：

1. 对 $i=1$ 和 $j=2$ 执行操作：$$[1, 2, 2, 1] \quad \rightarrow \quad [0, 3, 2, 1]$$
2. 对 $i=3$ 和 $j=2$ 执行操作：$$[0, 3, 2, 1] \quad \rightarrow \quad [0, 4, 1, 1]$$
3. 对 $i=3$ 和 $j=2$ 执行操作：$$[0, 4, 1, 1] \quad \rightarrow \quad [0, 5, 0, 1]$$

此时 $\max(0, 5, 0, 1) = 5$，因此答案为 5。