Natasha has just been assigned a very important job: illuminating the main square of Melbourne.

Naturally, she begins the only reasonable way: by putting on ...Baby One More Time by Britney Spears, turning the volume up, and getting to work. The square is huge, the night is getting darker, and Natasha is determined to make every part of it shine.

Around the square, there are ~n~ streetlights, numbered from ~1~ to ~n~ in clockwise order. Each streetlight has a cost to turn on, but the city budget is not unlimited. Luckily, each streetlight is powerful enough to light not only the area beneath itself, but also the areas beneath its two neighbouring streetlights.

The streetlights are arranged in a circle:

• if the next streetlight after ~n~ is needed, it is considered to be streetlight ~1~;
• if the previous streetlight before ~1~ is needed, it is considered to be streetlight ~n~.

You are given the cost ~c_i~ of turning on each streetlight ~i~. Natasha wants to choose some streetlights to turn on so that the area under every streetlight is lit, while minimizing the total cost.

For each test case, determine the minimum possible total cost.

Input

The first line contains an integer ~t~ ~(1 \le t \le 2\times 10^5)~, the number of test cases.

For each test case:

• The first line contains an integer ~n~ ~(1 \le n \le 2\times 10^5)~, the number of streetlights.
• The second line contains ~n~ integers ~c_1, c_2, ..., c_n~, where ~c_i~ ~(1 \le c_i \le 10^6)~ is the cost of turning on streetlight ~i~.

The sum of ~n~ over all test cases is at most ~2\times 10^5~.

Output

For each test case, print a single integer: the minimum total cost needed to make the whole square lit.

Sample Input

5
5
1 1 1 2 2
3
3 4 7
5
7 5 4 1 1
1
100
7
4 4 4 4 4 4 4

Sample Output

2
3
5
100
12

Explanation

In the first test case, we can turn on streetlights ~1~ and ~3~. The total cost is ~c_1 + c_3 = 1 + 1 = 2~, and every area is lit.

In the second test case, turning on only streetlight ~1~ is enough to light all areas, so the answer is ~3~.

In the third test case, we can turn on streetlights ~3~ and ~5~. The total cost is ~c_3 + c_5 = 4 + 1 = 5~.

In the fourth test case, there is only one streetlight, so we must turn it on. The answer is ~100~.

In the fifth test case, at least three streetlights are needed. Turning on streetlights ~1~, ~4~, and ~7~ gives total cost ~4 + 4 + 4 = 12~.