为了庆祝她的生日,亚丝娜的每位 $$$n$$$ 崇拜者都送给她一座塔。从第 $$$i$$$ 位崇拜者开始,塔的高度等于 $$$a_i$$$。
亚丝娜对收到的礼物的美丽程度评价为$$$\max(a_1, a_2, \ldots, a_n)$$$。她可以执行以下操作任意次数(可能为零)。
- 取 $$$1 \le i \neq j \le n$$$ 使得 $$$a_i + a_j$$$ 为奇数且 $$$a_i \gt 0$$$,然后将 $$$a_i$$$ 减少 $$$1$$$ 并增加 $$$a_j$$$ $$$1$$$。
帮助亚丝娜在多次操作后找到礼物的最大可能的美丽!
输入
每个测试由多个测试用例组成。输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 亚丝娜的崇拜者数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n \ (1 \le a_i \le 10^9)$$$ — 塔的高度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数:亚丝娜可以达到的礼物美感的最大值。
示例
输入复制
435 3 923 241 2 2 155 4 3 2 9
输出复制
9 5 5 21
注意
在第一个测试用例中,没有一对塔满足应用操作所需的条件,因此无法执行任何操作。在这种情况下,答案是 $$$\max(5, \ 3, \ 9) = 9$$$。
在第二个测试用例中,$$$i = 2$$$ 和 $$$j = 1$$$ 的运算可以应用两次。之后数组就变成:$$$a==\[5,\0]$$$。因此,答案是5。
在第三个测试用例中,可以应用以下操作序列:
- 操作$$$i=1$$$ 和$$$j=2$$$。
$$$[1, \ 2, \ 2, \ 1] \quad \rightarrow \quad [0, \ 3, \ 2, \ 1]$$$
- $$$i=3$$$ 和 $$$j=2$$$ 的操作。
$$$[0, \ 3, \ 2, \ 1] \quad \rightarrow \quad [0, \ 4, \ 1, \ 1]$$$
- $$$i=3$$$ 和 $$$j=2$$$ 的操作。
$$$[0, \ 4, \ 1, \ 1] \quad \rightarrow \quad [0, \ 5, \ 0, \ 1]$$$
$$$\max(0, \ 5, \ 0, \ 1) \ = \ 5$$$。
因此,答案是 5。