third

Captain Jack is a fearless pirate. He is known for his acts of valour. This time he has decided to prove his mettle in the waters of Caribbean sea. There are N pirates in the Caribbean sea. He can win a battle with a pirate x if and only if he has not fought a battle with pirate directly before the current one(i.e. pirate x-1). Each pirate has some treasure in his chest, If you defeat a pirate you get that treasure. You are a strategist of Jack, so you have calculate the maximum amount of treasure that you can loot.

INPUT
The first line of the input contains t ( the number of test cases). Each test case starts with a number N, the number of pirates. The next line will have N space separated integers representing the amount of treasure each pirate has. Pirates are described in the order they are encountered.

OUTPUT
Output contains t lines. Each line containing the maximum value corresponding to its test case.

CONSTRAINTS 
0 ≤ N ≤ 10^4        
0 ≤ The amount of treasure each pirate has ≤ 10^5         
1 ≤ t ≤ 10

SAMPLE INPUT
2
6
1 2 3 4 5 6
3 
15 10 5

SAMPLE OUTPUT
12
20

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: