D. Уничтожение полей одуванчиков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У фермера Джона есть газонокосилка, изначально выключенная. У него также есть $$$n$$$ полей, на $$$i$$$-м поле растет $$$a_i$$$ одуванчиков. Он посетит все поля в любом порядке, который захочет, и каждое поле ровно один раз.

У газонокосилки, кажется, есть собственный разум. Прямо перед посещением поля она проверяет, четное или нечетное на поле количество одуванчиков. Если одуванчиков нечетное количество, то газонокосилка переключает свое состояние (если она выключена, она включается; если она включена, она выключается). Затем, если газонокосилка включена, она срежет все одуванчики на этом поле. В противном случае, если газонокосилка выключена, ФД просто посетит поле и не срежет ни одного одуванчика.

Если ФД посетит $$$n$$$ полей в оптимальном порядке, каково максимальное общее количество одуванчиков, которое он сможет срезать?

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество полей.

Следующая строка содержит $$$n$$$ целых чисел, разделенных пробелами $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — количество одуванчиков на каждом поле.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
3
3
2 4 6
4
4 2 1 6
4
1000000000 999999999 1000000000 999999999
Выходные данные
0
13
2999999999
Примечание

Для первого набора входных данных, поскольку нет поля с нечетным количеством одуванчиков, ФД никогда не сможет включить свою газонокосилку. Поскольку его газонокосилка всегда выключена, он никогда не сможет срезать ни одного одуванчика, поэтому ответ $$$0$$$.

Для второго набора входных данных ФД может сначала посетить третье поле; тогда его газонокосилка включится. Затем он может посетить остальные поля в любом порядке. Поскольку его газонокосилка всегда включена, одуванчики на каждом поле могут быть срезаны.

Для третьего набора входных данных ФД может посетить поля в следующем порядке: поле $$$2$$$, поле $$$1$$$, поле $$$3$$$, затем поле $$$4$$$.