Maximum Even-Length Subsequence Sum

You are given t test cases. In each test case, you are provided with a sequence of non-negative integers. Your task is to find the maximum sum of any even-length subsequence of the given sequence.

An even-length subsequence is defined as a subsequence containing an even number of elements. To achieve the maximum sum, you are allowed to reorder the sequence. In other words, the optimal strategy is to select the largest even number of elements from the sequence. If the sequence has an odd number of elements, you must drop the smallest element among the selected ones to maintain even count.

For example, given the sequence [1, 2, 3, 4] (with 4 elements), the maximum sum is obtained by taking all elements: 1 + 2 + 3 + 4 = 10. However, for a sequence like [3, 3, 1, 7, 5] (with 5 elements), you would drop the smallest element among the top four elements after sorting in descending order, resulting in a sum of 18.

inputFormat

The input begins with an integer t, representing the number of test cases. Each test case follows and consists of two lines:

1. The first line contains a single integer n, the number of elements in the sequence.
2. The second line contains n space-separated non-negative integers.

outputFormat

For each test case, output a single integer on a new line representing the maximum sum of an even-length subsequence.

## sample

2
4
1 2 3 4
5
3 3 1 7 5

10
18

</p>