Maximum Sum of Non-Adjacent Subsequence

You are given an array of non-negative integers. Your task is to find the maximum possible sum of a subsequence such that no two numbers in the sequence are adjacent in the original array.

Formally, let the array be \(a_1, a_2, \dots, a_n\). You need to choose a subset of indices \(\{i_1, i_2, \dots, i_k\}\) such that for all \(j\), \(|i_{j} - i_{j-1}| \ge 2\). The goal is to maximize the sum \(\sum_{j=1}^{k} a_{i_j}\).

A typical recurrence for this problem is given by:

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

with the initial conditions \(\text{dp}[0] = a_0\) and \(\text{dp}[1] = \max(a_0, a_1)\). Your task is to implement this algorithm to handle multiple test cases.

inputFormat

The input is given via standard input and has the following format:

T
n_1
a11 a12 ... a1n1
n_2
a21 a22 ... a2n2
... 
n_T
aT1 aT2 ... aTnT

Here, T is the number of test cases. For each test case, the first line contains an integer n (the length of the array), and the second line contains n space-separated non-negative integers.

outputFormat

For each test case, output the maximum sum of a subsequence (one per line) computed as described above. The result for each test case should be printed on its own line.

## sample

2
4
3 2 5 10
3
3 2 7

13
10

</p>