Maximum Sum of Non-Adjacent Elements

You are given a list of integers and your task is to compute the maximum sum you can obtain by summing up a subsequence of non-adjacent elements. In other words, if you choose an element at index i, you cannot choose the elements at indices i-1 and i+1.

The problem can be modeled using dynamic programming. The recurrence relation is given by:

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

where \(dp[i]\) represents the maximum sum that can be obtained considering elements up to index \(i\) and \(a_i\) is the \(i^{th}\) element of the list. Assume that when the list is empty, the answer is 0, and if the list contains one element, the answer is \(\max(0, a_0)\).

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. Each test case is described as follows:

• The first line contains an integer \(n\), the number of elements in the list.
• The second line contains \(n\) integers separated by spaces.

outputFormat

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

## sample

1
4
3 2 5 10

13

</p>