The Night Thief

Problem Description

Ah Fu is an experienced burglar. Under cover of a dark night he plans to rob the shops along a street.

There are $N$ shops on the street, and each shop keeps some cash. Ah Fu has learned that the alarm system only triggers when he robs two adjacent shops at the same time — in which case the police will swarm in.

Ah Fu always works cautiously and does not want to risk being chased by the police. He wants to know the maximum amount of cash he can take tonight without alerting the police.

Input Format

The first line is an integer $T$ ($T \le 50$), the number of test cases.

For each test case: the first line is an integer $N$ ($1 \le N \le 100000$), the number of shops; the second line contains $N$ positive integers separated by spaces, the amount of cash in each shop. The cash in each shop does not exceed $1000$.

Output Format

For each test case output one line containing an integer: the maximum cash Ah Fu can take without alerting the police.

Sample Input

2
3
1 8 2
4
10 7 6 14

Sample Output

8
24

Hint

For the first sample, Ah Fu robs shop $2$ and gets $8$.

For the second sample, Ah Fu robs shops $1$ and $4$, getting $10+14=24$.

Limitation

1 s, 1024 KiB for each test case.