Problem Statement

You are given a positive integer $N$ and a length-$N$ sequence of positive integers $C=(C_1,C_2,\ldots,C_N)$.

You want to prepare one or more cards, as many as you like, and write one integer between $1$ and $N$ (inclusive) on each of the front and back sides of each card, so that the following condition is satisfied.

• No matter which distinct integers $x$ and $y$ between $1$ and $N$ (inclusive) are chosen, there exists at least one card satisfying the following.
• Exactly one of $x$ and $y$ is written on at least one side of that card.

It is allowed to write the same integer on the front and back of a single card.

Here, the cost of writing $a$ on the front and $b$ on the back of a card is $C_a+C_b$.

Find the minimum total cost required to satisfy the condition.

You are given $T$ test cases; solve each of them.

Constraints

• $1\le T\le 10^5$
• $2\le N\le 2\times 10^5$
• $1\le C_i\le 10^9$
• The sum of $N$ over all test cases is at most $2\times 10^5$.
• All input values are integers.

Input

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
C_1 C_2 \ldots C_N

Output

Output the answers for the test cases in order, separated by newlines.