Maximum Subarray Sum with Even Index Sum

You are given an array of integers. Your task is to find the maximum sum of any contiguous subarray such that the sum of the subarray's starting and ending indices is even. In other words, for a subarray defined by indices i and j (0 \leq i \leq j < n), the subarray is valid if:

\( (i + j) \bmod 2 = 0 \)

You need to determine the maximum sum among all valid subarrays. If no valid subarray is found, consider that scenario according to the constraints provided (though in this problem, a valid subarray always exists since a single element subarray is valid if 2i is even, which is always true).

Note: The indices are 0-based.

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each test case is described as follows:

• The first line of each test case contains an integer n, the size of the array.
• The second line contains n space-separated integers representing the elements of the array.

For example, a test case might look like:

5
3 -2 5 -1 2

outputFormat

For each test case, output a single line containing the maximum sum of a subarray where the sum of the starting and ending indices is even.

For example, for the given test case, the output would be:

7

## sample

5
5
3 -2 5 -1 2
4
-1 4 -3 5
5
1 2 3 4 5
5
1 -1 1 -1 1
5
-5 -4 -3 -2 -1

7
6
15
1
-1

</p>