Maximum Non-Adjacent Sum

You are given an array of integers and you need to select a subset of these integers such that no two selected elements are adjacent in the array. The goal is to maximize the sum of the selected elements.

More formally, if you denote the given array as \(a_1, a_2, \ldots, a_n\), you need to compute the maximum sum \(S\) where

\[ S = \max \{a_{i_1} + a_{i_2} + \cdots + a_{i_k} : i_{j+1} - i_j > 1 \text{ for all } j\} \]

Note that if all numbers are negative, the answer is 0 (i.e. you may choose no element at all).

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(T\) denoting the number of test cases. Each test case consists of the following:

• The first line contains an integer \(n\) — the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

For each test case, output a single integer on a new line — the maximum sum of non-adjacent elements.

## sample

1
4
3 2 5 10

13

</p>