Maximum Sum of Non-Adjacent Numbers

Given a list of integers (nums), find the maximum sum that can be obtained by summing a subset of these integers such that no two chosen elements are adjacent in the original list. More formally, if the indices of the chosen elements are (i_1, i_2, \ldots, i_k), then for every (j), (i_{j+1} \neq i_j + 1). If the list is empty or if all numbers are negative, the maximum sum is defined to be (0).

inputFormat

The input begins with 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 list. The second line contains (n) space-separated integers representing the list (nums). If (n = 0), the second line will be empty.

outputFormat

For each test case, output a single integer on a new line --- the maximum sum of non-adjacent numbers in the list.## sample

1
5
3 2 5 10 7

15