Description

A-Fu is an experienced thief. Taking advantage of the dark and windy night, A-Fu plans to rob the shops on a street tonight.
There are a total of N shops on this street, each containing some cash. A-Fu's prior investigation revealed that the street's alarm system will only activate when he robs two adjacent shops simultaneously, prompting the police to swarm in.
As a cautious thief, A-Fu is unwilling to risk being chased by the police. He wants to know: what is the maximum amount of cash he can obtain tonight without alerting the police?

Input Format

The first line of input is an integer T (T ≤ 50), indicating the number of test cases.
For each test case, the first line is an integer N (1 ≤ N ≤ 100,000), representing the total number of shops.
The second line consists of N positive integers separated by spaces, denoting the amount of cash in each shop.
The cash amount in each shop does not exceed 1000.

Output Format

For each test case, output one line. The line should contain an integer, representing the maximum amount of cash A-Fu can obtain without alerting the police.

2
3
1 8 2
4
10 7 6 14

8
24

Hint

For the first sample input, Ah Fu chooses to rob the second shop, obtaining a cash amount of 8.
For the second sample input, Ah Fu chooses to rob the first and fourth shops, obtaining a cash amount of 10 + 14 = 24.