Maximize the Stars

In this problem, you are given a series of stages, each with a certain number of stars. Your task is to compute the maximum number of stars you can collect if you are not allowed to pick two adjacent stages. More formally, given an array (a_1, a_2, \dots, a_N) where each (a_i) represents the stars at stage (i), you must choose a subset of these stages such that no two chosen stages are consecutive and the sum of the stars is maximized. This is a classic dynamic programming problem.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T), the number of test cases. Each test case begins with an integer (N) denoting the number of stages, followed by (N) non-negative integers representing the number of stars at each stage. For example, an input may look like:

T N stars_1 stars_2 ... stars_N

for each test case.

outputFormat

For each test case, output a single line to standard output (stdout) containing the maximum number of stars that can be collected by selecting non-adjacent stages.## sample

1
4
1 2 9 4

10