Chocolate Day
/
No tags
Problem
Editorial
Analytics

It’s 9th of February, Chocolate Day of valentine week!!!

Pařømîtå has “acute weakness” for chocolates. Now, as it is Valentine Week, so everyone in the CSE dept is tensed about getting a valentine by 14th. As Pařømîtå’s love for chocolates is well known to everyone, all the N boys of CSE dept have thought of impressing her by giving a huge number of chocolates to her on Chocolate Day.

Each of the N boys seated in a row have decided to give Ci number of chocolates. Now Pařømîtå sees a great opportunity to have large number of chocolates just for her. So she has decided to try to have maximum number of chocolates. But, again, if she takes chocolates from two adjacent seated boys, they would be feeling heartbroken. So, she doesn’t want to hurt anybody’s feelings. She falls in a dilemma thinking about how many maximum chocolates she can get in this given situation.

So she has approached you to solve this dilemma and help her know the maximum number of chocolates she can get.

INPUT
The input will start with a single integer T, denoting the number of test cases. Each test case will consist of two lines. First line will have a single integer N, denoting number of boys offering chocolates. Next line will contain N integers Ci separated by a single space, each denoting the number of chocolates offered by ith boy.

OUTPUT
For each test case, output a single integer denoting the maximum number of chocolates in a new line.

CONSTRAINTS

• 1<=T<=1000
• 1<=N<=50000
• 0<=Ci<=105
SAMPLE INPUT
1
5
1 3 7 8 12
SAMPLE OUTPUT
20
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...