Tom Dwan has long been considered one of the most aggressive poker players in the world, and his mind-boggling swings are proof. Apparently, he is the most feared poker player at present with a net worth of $ 10 Million. Because of his good guessing power and confidence to rely on it, not only his wins, but his folds are also epic.

One evening while playing poker he made a terrible mistake and lost all the chips to his opponents. In order to get more chips he went to play a game.

There are N pots placed in a circle, ith pot contains Ai number of chips. Dwan can pick any number of the pots, but he is not allowed to choose adjacent pots. What is the maximum number of chips he could collect?

Input

First line contains single integer T denoting the number of test cases. The first line of each test case contains a single integer N denoting the number of pots. The second line contains N space-separated integers A1, A2, ..., AN denoting the number of chips in each pot.

Output

For each test case, output a single line containing an integer corresponding to the maximum number of chips he could collect.

Constraints

1 <= T <= 110

2 <= N <= 2.5*10^4

1 <= Ai <= 10^7

Use Fast I/O