Optimal Candy Collection

You are given several test cases. In each test case, you are given an integer n and an array A of n integers where A[i] represents the number of candies available in the i-th house.

You need to collect as many candies as possible under a magical constraint: if you collect candies from house i, you cannot collect candies from its immediate neighbors, i.e., houses i-1 and i+1. This can be formulated using dynamic programming. Let \(dp[i]\) represent the maximum candies that can be collected from houses 1 to \(i\). The recurrence relation is given by:

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

with the base cases \(dp[0] = A[0]\) and \(dp[1] = \max(A[0], A[1])\). Your task is to compute the maximum candies that can be collected for each test case.

inputFormat

The input begins with a single integer T on the first line, the number of test cases. For each test case, the first line contains an integer n (the number of houses). The second line contains n space-separated integers, where the i-th integer represents the number of candies at the i-th house.

outputFormat

For each test case, output a single line containing the maximum number of candies that can be collected, following the rule that if you choose to collect candies from a house, you cannot collect from its immediate neighbors.

## sample

3
3
6 7 1
4
2 1 5 8
5
3 2 5 10 7

7
10
15

</p>