Maximum Points in Levels

You are given T test cases. In each test case, you are provided with an integer N which represents the number of levels in a game and a list of N integers where each integer represents the points available at that level.

You cannot complete two consecutive levels, so you must choose levels in such a way that maximizes your total points. The problem is a classic dynamic programming challenge. The recurrence relation used to solve the problem is given by

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

with initial conditions

$$dp[0] = a_0, \quad dp[1] = \max(a_0, a_1)$$

Your task is to compute and output the maximum points that can be accumulated for each test case.

inputFormat

The first line of the input contains an integer T, representing the number of test cases. Each test case consists of two parts:

• An integer N representing the number of levels.
• N integers separated by spaces, where each integer represents the points available at that level.

All values are provided via standard input (stdin).

outputFormat

For each test case, output a single line containing one integer: the maximum points that can be obtained by choosing non-adjacent levels optimally. The output is printed to standard output (stdout).

## sample

1
1 5

5

</p>