Maximum Non-Adjacent Route Points

You are given several competitions. In each competition, a participant can choose a series of routes where each route awards a certain number of points. However, if a route is chosen, the next route cannot be chosen (i.e., consecutive selections are disallowed). The task is to calculate the maximum points a participant can earn for each competition by selecting non-adjacent routes.

More formally, for each competition represented as an array of integers \(a_1, a_2, \ldots, a_n\), you are required to compute the maximum sum of points by selecting some routes such that no two selected routes are consecutive. In case there are no routes available (i.e., the competition array is empty), the maximum points are 0.

The input begins with an integer \(T\) representing the number of competitions. For each competition, the first number is \(N\) (the number of routes), followed by a line containing \(N\) integers detailing the points for each route. The output for each competition should be printed on a separate line.

Example:

Input:
1
3
10 20 30

Output:
40

inputFormat

The input is provided via standard input (stdin) and is structured as follows:

• The first line contains an integer \(T\) denoting the number of competitions.
• For each competition:
• The first line contains an integer \(N\) indicating the number of routes.
• The second line contains \(N\) space-separated integers representing the points for each route.

outputFormat

For each competition, output the maximum points that can be accumulated by selecting non-adjacent routes. Each result should be printed on a new line to standard output (stdout).

## sample

1
1
10

10

</p>