Maximum Sum of Non-Adjacent Elements

You are given an array of integers. Your task is to find the maximum sum you can obtain by summing a subsequence in which no two elements are adjacent in the original array. In other words, if you select an element at index i, you cannot select elements at index i-1 or i+1.

The problem can be solved using dynamic programming. Let \(dp[i]\) represent the maximum sum considering the first i elements. The recurrence relation is given by:

[ dp[i] = \max(dp[i-1], dp[i-2] + a_i) ]

with the base cases \(dp[0] = 0\) and \(dp[1] = \max(0, a_0)\). Note that if all numbers are negative, choosing no element (i.e. sum = 0) might be optimal.

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer N indicating the number of elements in the array.
• The second line contains N space-separated integers representing the array elements.

It is guaranteed that the input follows this format.

outputFormat

For each test case, output a single integer — the maximum sum that can be obtained by summing non-adjacent elements. Each result should be printed on a new line.

## sample

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

13
8
2

</p>