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