C. Асуна и комары
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Асуне на день рождения каждый из $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: максимальное значение красоты подарков, которое Асуна сможет получить.

Пример
Входные данные
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$$$ два раза. После чего массив станет таким: $$$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.