Max Gold Protected

You are given a set of houses arranged in a row. Each house has a certain amount of gold stored in it. Due to security restrictions, two adjacent houses cannot both be fully protected by guards. Your task is to determine the maximum amount of gold that can be protected in each scenario if guards are positioned in an optimal way.

Formally, for a given array of non-negative integers \(a_1, a_2, \dots, a_n\) representing the amount of gold in each house, you need to compute the maximum sum of gold you can obtain under the constraint that you cannot pick two consecutive houses. The recurrence relation for the dynamic programming solution is given by:

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

where \(dp[i]\) represents the maximum gold that can be secured from the first \(i\) houses, with the conventions \(dp[0] = a_1\) and \(dp[1] = \max(a_1, a_2)\). For the special case when there are no houses (i.e. \(n = 0\)), the maximum gold protected is 0.

You will be given multiple test cases. For each test case, the first integer is \(n\), followed by \(n\) integers representing the gold values for each house.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains an integer \(T\) representing the number of test cases.
• For each test case, there is a line containing an integer \(n\) (the number of houses).
• This is followed by a line containing \(n\) space-separated integers, where each integer represents the amount of gold in a house.

outputFormat

For each test case, output the maximum amount of gold that can be protected, each on a new line, to standard output (stdout).

## sample

3
4
5 5 10 100
3
1 2 3
5
10 1 10 1 10

105
4
30

</p>