19355번 - A Really Odd Sequence 다국어

문제

According to our long-established tradition, the best statements are those kept short.

Given a sequence of integers, find the largest sum of a consecutive subsequence of odd length.

입력

The first line of input contains the number of test cases $z$. The descriptions of the test cases follow.

The first line of each test case contains the length of the sequence $n$ (1ドル \leq n \leq 1,000円,000円$).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$), the elements of the sequence.

The total length of all sequences in all test cases does not exceed 5ドル,000円,000円$.

출력

For each test case, output the largest sum on a separate line.

제한

힌트