Taco's Petals Collection

A garden is full of flowers, and each flower has a petal with a certain power value. A bee named Taco wants to collect these petals to maximize her total power. However, Taco cannot collect petals from two consecutive flowers because doing so will alert predators.

Your task is to determine the maximum total power value that Taco can collect by picking petals such that no two consecutive flowers are chosen. This problem can be solved using dynamic programming. In particular, you can use the recurrence relation

[ \text{dp}[i] = \max(\text{dp}[i-1],; \text{dp}[i-2] + a_i) ]

where (a_i) is the power value of the (i^{th}) flower. Note that when there is only one flower, Taco will simply take that petal, and if there are no flowers, the answer is 0.

inputFormat

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

• The first integer is \(N\) representing the number of flowers.
• Then follow \(N\) space-separated integers, each representing the power value of a petal for each flower.

All input values are provided via standard input (stdin).

outputFormat

For each test case, output a single line containing one integer — the maximum total power value that Taco can collect, printed to standard output (stdout).

## sample

2
5 2 5 1 2 6
4 1 2 9 4

11
10

</p>