Maximum Non-Consecutive Sum

In this problem, you are given several test cases. Each test case consists of a list of participants' skill levels. Your task is to select a subset of these participants such that no two selected participants have consecutive positions in the list, and the resulting sum of their skills is maximized. This can be solved using dynamic programming. The recurrence relation is given by ( dp[j] = \max(dp[j-1], dp[j-2] + \text{skills}[j]) ), where ( dp[j] ) represents the maximum sum that can be achieved considering the first ( j+1 ) elements.

inputFormat

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 participants. The next line contains ( N ) space-separated integers representing the skill levels.

outputFormat

For each test case, output a single line containing the maximum sum of skills obtainable under the condition that no two selected participants are consecutive.## sample

1
5
3 2 5 10 7

15