Ghost Hunters

You are given a row of haunted houses, each containing a certain number of ghosts. Your mission is to determine the maximum number of ghosts that can be eliminated without triggering an alarm. The rule is that if you eliminate ghosts from one house, you cannot eliminate ghosts from its directly adjacent houses.

This problem can be modeled using dynamic programming. The recurrence relation is given by: $$ dp[i] = \max(dp[i-1], dp[i-2] + a_i) $$ for \( i \ge 2 \) with the base cases defined as \( dp[0] = a_0 \) and \( dp[1] = \max(a_0,a_1) \), where \( a_i \) is the number of ghosts in the \( i^{th} \) house.

inputFormat

The first line contains an integer \( t \) representing the number of test cases. For each test case, the first line contains an integer \( n \) indicating the number of houses. The next line contains \( n \) space-separated integers, where each integer represents the number of ghosts in a house.

outputFormat

For each test case, output a single integer — the maximum number of ghosts that can be eliminated. Each output should be printed on a new line.

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

15
11