House Robber Problem

You are given a row of houses, where each house contains some amount of money. Your task is to determine the maximum amount of money you can rob tonight without alerting the police. The constraint is that you cannot rob two adjacent houses.

The problem can be expressed using the following recurrence relation in latex:

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

For each test case, the input starts with an integer n, representing the number of houses, followed by n space-separated integers indicating the amount of money stored in each house.

inputFormat

The first line of the input contains an integer T, the number of test cases. Each of the following T lines represents a test case and starts with an integer n (the number of houses), followed by n integers that denote the amount of money in the houses.

outputFormat

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

## sample

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

4
12
3

</p>