Manish wants to make a bouquet of flowers for someone so he goes to a flowershop. There he sees the flowers are kept in a row and have some value attached to each flowers. Consider number of roses to be n and each rose has a market value of a[i], where 0<=i<n.

What can be the  maximum cost if he can make his bouquet by selecting any flower given without plucking any two adjacent flowers.

NOTE: Use fast i/o to get your answer

Constraints:

1<= T <= 1000,

1<= N <= 10^4,

1<= a[i] <= 100

Input Format:

First line contains 'T' - no. of test cases

Each testcase contains 2 lines

First line contains 'N' total flowers.

Second line contains an array of size n, each element of array representing price of flower.

Output Format:

'T' lines, each containing maximum cost.