F. Mr.Wow and Decoding
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr.Wow has an $$$0$$$-indexed integer array $$$b=[b_0, b_1, .... , b_{n-2}, b_{n-1}]$$$ containing $$$n$$$ elements. It is guaranteed that $$$n$$$ is even.

An array $$$a$$$ of size $$$n$$$ is called valid only if:

  • For every $$$0 \le i \le n-1$$$,
    1. $$$0 \le a_i \le 10^{18}$$$.
    2. $$$b_{i} \le (a_{i} + a_{i+1} + \ldots + a_{(i+(\frac{n}{2})-2)\%n} + a_{(i+(\frac{n}{2})-1)\%n})$$$ holds.

Here $$$\%$$$ represents the modular operation.

Find the minimum value of $$$(a_0+a_1+\ldots+a_{n-1})$$$ among all valid array $$$a$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the length of the array $$$a$$$. It is guaranteed that $$$n$$$ is even.

The second line of each test case contains $$$n$$$ space separated integers $$$b_{i}$$$ ($$$0 \le b_{i} \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum value of $$$(a_0+a_1+\ldots+a_{n-1})$$$ among all valid array $$$a$$$.

Example
Input
4
6
1 2 3 4 5 6
6
7 3 5 12 15 10
8
7 0 8 8 0 0 0 10
10
0 0 100 0 0 67 0 4252 99 0
Output
9
19
18
4352
Note

In the $$$1$$$-st test case, one of the possible arrays is $$$a = [0,0,3,0,0,6]$$$.

In the $$$2$$$-nd test case, one of the possible arrays is $$$a = [6,1,0,2,3,7]$$$.