Maximum Money Robbery

You are given an array of integers representing the amount of money available in each house along a street. However, you cannot rob two adjacent houses because robbing adjacent houses will trigger an alarm. Your task is to calculate the maximum amount of money that can be stolen without alerting the police.

More formally, given an array ( A ) of length ( N ), find the maximum sum ( S ) such that no two elements contributing to ( S ) are adjacent in the original array.

inputFormat

The first line contains a single integer ( T ), the number of test cases.\nFor each test case:\n- The first line contains an integer ( N ), the number of houses.\n- The second line contains ( N ) space-separated integers representing the money in each house.

outputFormat

For each test case, print a single integer representing the maximum amount of money that can be robbed.## sample

1
7
6 7 1 30 8 2 4

41