C. Red Pandacakes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Two red pandas, Oscar and Lura, enjoy pancakes. In fact, they enjoy pancakes so much that they live in a giant circular pancake town called Pandacake. In Pandacake, there are $$$n$$$ pancake stores around the perimeter of the town, labeled $$$1$$$ through $$$n$$$ in clockwise order. The $$$i$$$th store has $$$p_i$$$ pancakes in stock.

Oscar and Lura each want as many pancakes as they can get. They collect pancakes as follows. At the beginning, Lura chooses a store first, and then Oscar chooses a different store.

Afterwards, they move as follows:

  1. Lura chooses a store that neither red panda has gone to, and she can walk to without crossing any of Oscar's stores. Then, she visits all the stores along the way.
  2. Oscar chooses a store that neither red panda has gone to, and he can walk to without crossing any of Lura's stores. Then, he visits all the stores along the way.

In each store that a red panda visits, he or she will buy all of the pancakes in stock. Please help Lura maximize the number of pancakes she gets.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$).

The second and final line of every test case includes $$$n$$$ integers $$$p_1, \: p_2, \: p_3, \ldots \: p_n$$$, the number of pancakes in stock at the $$$i$$$th store.

It is guaranteed that the sum of all $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one number: the maximum pancakes that Lura can get.

Example
Input
4
2
50 49
3
50 49 50
4
50 49 50 49
9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Output
50
99
99
5000000000