Little C has ~n~ books, each with a weight, and he decides to merge them into a pile.

Each time when Little C merges, he can put one pile of books on top of another to merge them into one pile. If Little C puts the ~i~-th pile of books on top of the ~j~-th pile of books, the energy Little C needs to consume is the weight of the ~i~-th pile of books plus the wear value of the two piles of books.

Initially, each book is in its own pile and the wear values are all ~0~. Whenever Little C merges two piles of books, the wear value of the new pile of books formed is twice the larger of the wear values of the two piles of books before merging, plus one. The weight of the new pile of books is the sum of the weights of the two piles of books before merging.

Your task is to design a merging order to minimize the total energy consumption of Little C and output the minimum total energy consumption.

Input Specification

This problem has multiple test data sets.

The first line of the input contains an integers ~t~, which represents the number of test data sets.

Then, each set of test data is given as input in order. For each set of test data:

The first line of input contains a positive intege ~n~, which represents the number of books.

The second line of input contains ~n~ positive integers ~w_1,w_2,\dots,w_n~, where ~w_i~ represents the weight of the ~i~-th book.

Output Specification

For each set of test data, output a line containing an integer, representing the minimum total energy consumption.

Sample Input 1

1
4
1 1 1 1

Sample Output 1

6

Explanation for Sample Output 1

If Little C combines the four books in pairs and then combines the two pairs into one, the energy consumption of the first two merging operations is ~1~ each, and in the third time, a pile of books with weight of ~2~ is placed on top of the other pile. The wear value of the two piles of books is ~1~ each, and the energy consumption is ~2 + 1 + 1 = 4~. Therefore, if Little C chooses this plan, the total energy consumption is only ~1 + 1 + 4 = 6~. It can be proved that in the above sample, ~6~ is the minimum total energy consumption.

Additional Samples

Sample inputs and outputs can be found here.

• Sample 2 (ex_book2.in and ex_book2.ans).
• Sample 3 (ex_book3.in and ex_book3.ans).
• Sample 4 (ex_book4.in and ex_book4.ans).

Constraints

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

Test ID	~n\le~	Additional Constraints
~1 \sim 2~	~7~	None
~3~	~11~
~4~	~13~
~5 \sim 6~	~22~
~7 \sim 8~	~28~
~9 \sim 13~	~50~
~14~	~60~
~15~	~70~
~16~	~80~
~17 \sim 18~	~100~	A
~19 \sim 20~		None

Additional Constraint A: It is guaranteed that ~w_i=1~.