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

In each merge operation, Little C can place one stack of books on top of another to combine them into a single stack. If Little C places stack $i$ on top of stack $j$, the physical effort consumed is the weight of stack $i$ plus the sum of the wear values 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. The weight of the new stack 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.

Input

The input contains multiple test cases. 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 on a new line, representing the minimum physical effort required to merge the $n$ books into one stack.

Examples

Input 1

1
4
1 1 1 1

Output 1

6

Note

If Little C merges the 4 books in pairs and then merges the two resulting stacks into one: The physical effort for the first two merges is 1 each. For the third merge, placing a stack of weight 2 on top of another stack (where both stacks have a wear value of 1), the effort consumed is $2 + 1 + 1 = 4$. Therefore, if this strategy is chosen, the total physical effort consumed by Little C is $1 + 1 + 4 = 6$. It can be proven that in the example above, 6 is the minimum physical effort.

Constraints

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

Special property: Guaranteed $w_i = 1$.