Maximum Sum of Non-Adjacent Elements

You are given T test cases. For each test case, you are provided an array of integers. Your task is to compute the maximum possible sum by selecting a subset of elements such that no two chosen elements are adjacent in the original array.

In other words, if you choose the element at index \( i \), you cannot choose the elements at index \( i-1 \) or \( i+1 \). Note that you are allowed to choose an empty subset, which yields a sum of 0. This problem is a variation of the well-known House Robber problem and can be efficiently solved using dynamic programming techniques.

Input Constraints:

• The first line of input contains an integer \( T \), representing the number of test cases.
• For each test case, the first line contains an integer \( n \) (the number of elements in the array), followed by a line containing \( n \) space-separated integers.

Note: It is guaranteed that the size of each test case and the integers will be within reasonable limits to allow an efficient dynamic programming solution.

inputFormat

The input is read from stdin and is structured as follows:

T
n1
a1 a2 ... an1
n2
b1 b2 ... bn2
...

Here, \( T \) is the number of test cases. For each test case, the first line contains an integer \( n \) (the number of elements), followed by a line containing \( n \) space-separated integers.

outputFormat

For each test case, output the maximum sum obtainable where no two selected elements are adjacent. The result for each test case should be printed on a new line to stdout.

## sample

2
5
3 2 5 10 7
3
1 -1 3

15
4

</p>