Problem statement:
There are blocks of cheese of different weights placed in a line. A mouse would like to eat the cheese, but with some rules. The mouse can’t eat two consecutive cheese blocks. The mouse would like to eat maximum cheese from the line of cheese blocks. Weight of each cheese block in Kg is given as a[i] in an integer array.
Input:
The first line of input contains an integer T denoting the number of test cases. Each test case contains an integer n which denotes the number of elements in the array a[]. Next line contains space separated n elements in the array a[].
Output:
Print an integer which denotes the maximum amount of cheese that the mouse can have.
Constraints:
1<=T<=200
1<=n<=1000
1<=a[i]<=10000
Example:
Input:
2
6
8 5 10 100 10 5
3
1 2 3
Output:
113
4