Someone stopped setting problems, so I had to randomly modify a NOI problem statement.

Parts different from [NOI2023] Merging Books are bolded.

Little C has $n$ books, each with a certain weight, and he decides to merge them into a single stack.

In each merge, Little C can place one stack of books on top of another to combine them into one stack. If Little C places stack $i$ on top of stack $j$, the physical effort consumed is the wear value of stack $i$ plus the sum of the weights of the two stacks.

Initially, each book forms its own stack with a wear value of $0$. Whenever Little C merges two stacks, the wear value of the new stack formed is twice the maximum of the wear values of the two stacks before merging, plus one, and the weight is the sum of the weights of the two stacks before merging.

Your task is to design a merging sequence to minimize the total physical effort consumed by Little C and output this minimum value.

There are multiple test cases.

Input

The first line contains a positive integer $t$, representing the number of test cases.

For each test case:

The first line contains a positive integer $n$, representing the number of books.

The second line contains $n$ positive integers, where the $i$-th number $w_i$ represents the weight of the $i$-th book.

Output

For each test case, output a single integer representing the minimum physical effort required to merge the $n$ books into one stack.

Examples

Input 1

5
6
1 1 4 5 1 4
6
10 10 40 50 10 40
5
1000000000 1000000000 1000000000 1000000000 1000000000
6
1 3 15 105 945 27455185
6
1 2 3 4 5 6

Output 1

38
371
12000000001
27457470
52

Constraints

For all data, $\sum n^2 \leq 10^8$; $\sum n \leq 5 \times 10^5$; $1 \leq w_i \leq 10^9$.

There are 7 subtasks in total. The special constraints and scores for each subtask are as follows:

• Subtask 1 (5 pts): $n \leq 6, T \leq 5$
• Subtask 2 (15 pts): $n \leq 12, T \leq 5$
• Subtask 3 (15 pts): $n \leq 30, T \leq 5$
• Subtask 4 (15 pts): $n \leq 80, T \leq 5$
• Subtask 5 (20 pts): $\sum n^3 \leq 5 \times 10^7$
• Subtask 6 (5 pts): All $w_i$ within the same test case are identical.
• Subtask 7 (25 pts): No special constraints.

All reasonable subtask dependencies are enabled during evaluation.