Problem Description

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

Each time Little C can place a stack of books on top of another stack, merging them into one. If Little C places the $i$-th stack on top of the $j$-th stack, the energy he needs to consume is the weight of the $i$-th stack plus the sum of the wear values of both stacks.

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

Your task is to design a sequence of merges that minimizes the energy Little C consumes, and output this minimum energy consumption value.

Input Format

This problem contains multiple test cases.

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

For each test case:

The first line contains a positive integer $n$, indicating 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 Format

For each test case, output a single line containing an integer, which is the minimum energy required to merge the $n$ books into one stack.

Sample Input and Output

Sample Input #1

1
4
1 1 1 1

Sample Output #1

6

Sample Input #2

See the attached file book/book2.in.

Sample Output #2

See the attached file book/book2.ans.

Sample Input #3

See the attached file book/book3.in.

Sample Output #3

See the attached file book/book3.ans.

Sample Input #4

See the attached file book/book4.in.

Sample Output #4

See the attached file book/book4.ans.

Notes

[Sample Explanation #1]

If Little C merges the 4 books in pairs and then merges the resulting two stacks into one, the energy consumed in the first two merges is each $1$. The third merge involves placing a stack of weight $2$ on top of another stack, both with a wear value of $1$, requiring an energy consumption of $2 + 1 + 1 = 4$.

Thus, if this scheme is chosen, the total energy consumed by Little C is $1 + 1 + 4 = 6$.

It can be proven that $6$ is the minimum energy consumption value in this example.

[Data Range]

For all test data, it is guaranteed that: $1 \le t \le 10$, $1 \le n \le 100$, $1 \le w_i \le 10^9$.

Special Property: It is guaranteed that $w_i = 1$.

见题面 Input 部分

见题面 Output 部分