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

Подотрезок — это непрерывная часть массива.

Ярик недавно нашёл массив $$$a$$$ из $$$n$$$ элементов, и ему стало очень интересно найти сумму непустого подотрезка с максимальной суммой. Но Ярик не любит числа одной чётности, стоящие рядом, так что у подотрезка, который он выберет, чётности соседних элементов должны различаться.

Например, массив $$$[1, 2, 3]$$$ подойдёт, но $$$[1, 2, 4]$$$ не подойдёт, так как $$$2$$$ и $$$4$$$ — чётные числа и стоят рядом.

Вам нужно помочь Ярику и вывести максимальную сумму такого подотрезка.

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

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

В первой строке дано одно целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — длина массива.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(-10^3 \le a_i \le 10^3)$$$ — элементы массива.

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

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

Для каждого набора данных выведите одно число — ответ на задачу.

Пример
Входные данные
7
5
1 2 3 4 5
4
9 9 8 8
6
-1 4 -1 0 5 -4
4
-1 2 4 -3
1
-1000
3
101 -99 101
20
-10 5 -8 10 6 -10 7 9 -2 -6 7 2 -4 6 -1 7 -6 -7 4 1
Выходные данные
15
17
8
4
-1000
101
10