Problem description.
Tima wants to contest for Mr. Ignus. But there are many obstacles which Tima must cross to become Mr. Ignus. Tima has qualified and passed all the tests and there remains a last test for him to complete successfully. The task is as follows :
There are n judges. The ith judge have A[i] coins with him. Now Tima has to collect maximum coins from all the judges by following rules :.
He can collect all the coins from any judge. If he collects coins from ith judge then he shouldn't have collected coins from the judge just before the current one.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of judges. The second line contains N space-separated integers, number of coins each judge has

Output

For each test case, output a single line containing maximum number of coins Tima can collect.

Constraints
Should contain all the constraints on the input data that you may have. Format it like:

1 ≤ T ≤ 10
0 ≤ N ≤ 100000
0 ≤ A[i] ≤ 1000000000

Example
Input:
2
5
1 2 3 4 5
1
10

Output:
9
10

Explanation
Example Case 1.He can collect 1st, 3rd and 5th coin to receive total of (1+3+5) 9 coins

见题面

见题面