It’s 9^th 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 14^th. 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 C_i 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 C_i separated by a single space, each denoting the number of chocolates offered by i^th 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<=C_i<=10⁵