Problem Statement

You are given a length-$N$ positive integer sequence $A = (A_1, A_2, \ldots, A_N)$.

You are now standing at coordinate $0$ on the number line, and will perform the following operation any number of times:

• Choose any element $A_i$ from $A$ freely. Also, choose either positive or negative direction freely. Then, jump distance $A_i$ in the chosen direction.

You are interested in operation sequences that satisfy the following conditions:

• Perform the operation at least once and finally return to coordinate $0$.
• Never enter the negative region during the process.
• Never jump consecutively the same distance in different directions.

The cost of an operation sequence satisfying the conditions is the maximum value among the coordinates visited when moving according to that operation sequence. Find the minimum possible cost among operation sequences satisfying the conditions. Under the constraints of this problem, an operation sequence satisfying the conditions always exists.

Solve $T$ test cases for one input.

Constraints

• $1 \leq T \leq 125000$
• $2 \leq N \leq 250000$
• $1 \leq A_1 < A_2 < \cdots < A_N \leq 10^{18}$
• The sum of $N$ in one input does not exceed $250000$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N
A_1 A_2 \cdots A_N

Output

For each test case, output the answer.