House Robber Problem

You are given a row of houses, each containing a certain amount of money. You must determine the maximum amount of money you can rob without alerting the police, under the condition that you cannot rob two adjacent houses. In other words, if you rob house i, you cannot rob house i-1 or house i+1.

The problem can be formulated as follows: Given an integer sequence \(a_1, a_2, \ldots, a_n\) representing the amount of money in each house, compute the maximum sum \(S\) such that no two adjacent \(a_i\) are chosen. The recurrence relation is given by:

\[ dp[i] = \max(dp[i-1], dp[i-2] + a_i), \quad i \ge 1 \]

with the base cases \(dp[0] = 0\) and \(dp[1] = a_1\). You need to process multiple test cases.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(T\) representing the number of test cases. Each test case consists of two lines. The first line of each test case contains an integer \(N\) denoting the number of houses. The second line contains \(N\) space-separated integers representing the amount of money in each house.

outputFormat

For each test case, output a single line containing one integer, the maximum amount of money that can be robbed without alerting the police.

## sample

2
4
1 2 3 1
5
2 7 9 3 1

4
12

</p>