Maximum Subset Sum with No Adjacent Elements

You are given a list of integers. Your task is to select a subset of these integers such that no two selected elements are adjacent in the original list and the sum of the selected subset is maximized.

You can use dynamic programming to solve this problem. The recurrence relation is given by \[ dp[i] = \max(dp[i-1],\; dp[i-2] + a_i)\] where \(a_i\) is the \(i^{th}\) element of the list. If the list is empty, the answer is 0.

For each test case, you will be provided with an integer \(N\) (the number of elements in the list) followed by \(N\) space-separated integers. Print the maximum sum possible for each test case on a new line.

inputFormat

The input is read from stdin and has the following format:

T
N
a1 a2 ... aN
N
a1 a2 ... aN
...

Where:

• T is the number of test cases (T > 2).
• For each test case, the first line contains an integer N, the number of elements in the list.
• The next line contains N space-separated integers.

outputFormat

For each test case, output the maximum sum of a subset of non-adjacent elements on stdout. Each result should be printed on a new line.

## sample

3
4
1 2 9 4
5
3 2 5 10 7
4
2 1 4 9

10
15
11

</p>