Maximum Total Cost of House Painting

You are given a series of test cases. Each test case describes a row of houses along with the cost of painting each house. Your goal is to determine the maximum total cost of painting houses such that no two adjacent houses are painted on the same day.

This is essentially a variation of the classic house robber problem where you are not allowed to paint two consecutive houses, so you must decide which houses to paint in order to maximize the total cost.

The optimal solution can be obtained using a dynamic programming approach with the following recurrence:

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

where \(dp[i]\) denotes the maximum cost achievable from the first \(i+1\) houses.

inputFormat

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

The first line contains an integer (T), 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 representing the cost of painting each house.

For example:

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

outputFormat

For each test case, print the maximum total cost achievable on a new line (stdout).## sample

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

15
10