题目描述
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
输入格式
见题面
输出格式
见题面