Maximum Non-Adjacent Sum

Alex is playing a game with a sequence of numbers. The rule is that he can pick any number from the sequence, but once a number is picked, he cannot pick the immediate next or immediate previous number. Find the maximum sum Alex can obtain by selecting such numbers.

Let \(a_1, a_2, \dots, a_n\) be the sequence. You are required to compute the maximum sum where no two selected numbers are adjacent. Formally, define the recurrence relation as:

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

with appropriate base cases.

inputFormat

The first line of input contains an integer T (the number of test cases). For each test case:

• The first line contains an integer n, the number of elements in the sequence.
• The second line contains n space-separated integers representing the sequence.

outputFormat

For each test case, output a single line with the maximum sum obtainable under the given rules.

## sample

1
5
3 2 5 10 7

15

</p>