D. The Route of the 12 Lakes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Route of the 12 Lakes is a small mountain trail in France, very close to the border with Andorra. It consists of a circular route that can be walked or cycled, where along the way you can see 12 lakes.

Laura wanted to take this route but took the wrong road and ended up on the route of the $$$n$$$ lakes. This route is very similar to the one with 12 lakes but much longer. There are $$$n$$$ lakes, and between the $$$i$$$-th lake and the $$$(i+1)$$$-th lake, there is a path of $$$c_i$$$ kilometers. Between the $$$n$$$-th lake and the first, there is a path of $$$c_n$$$ kilometers.

Since this route is too long, there are different bus lines; each line goes from lake $$$l_1$$$ to lake $$$l_2$$$ via the shortest path (according to the circular route). There is a bus line for each pair of lakes, and each line operates in both directions.

Having gotten confused, Laura has lost her desire to walk. However, she still has the desire to see the area and take photographs, so she has decided to take advantage of the bus lines to enjoy the scenery. She wants to plan a route that meets the following conditions:

  • She can start from any lake but must end at the same lake.
  • She can take each bus line at most once in each direction.
  • She wants to cover the maximum number of kilometers.

Given these conditions, what is the maximum number of kilometers Laura can travel without walking?

Input

The input starts with an integer $$$t$$$ indicating the number of cases.

Each case begins with an integer $$$n$$$, and the following line contains the $$$n$$$ integers $$$c_i$$$.

Output

For each case, write a line with the result.

Scoring

$$$1 \leq t \leq 100$$$

$$$1 \leq c_i \leq 10^5$$$

8 Points: $$$2 \leq n \leq 7$$$

18 Points: $$$2 \leq n \leq 100$$$

28 Points: $$$2 \leq n \leq 1000$$$

46 Points: $$$2 \leq n \leq 10^4$$$

Example
Input
4
4
1 10 1 1
5
2 4 1 5 3
10
1 1 1 1 1 1 1 1 1 1
2
1 4
Output
20
88
250
2