The graduate season has coming. As a gift for his girlfriend, David Huffman wants to build a golden chain. After hard trying to look for cheap chains, he has gathered several chains in the same style. And now, he has to link these chains into one chain.
The store charges for every welding and only two chains can be linked together. Any time two chains are linked, the length of new chain is the sum of two chains. If David wants to link N chains, he must link N-1 times. You might be guessing how the store charges for linking 2 chains. As most of you are thinking, if the length of the first golden chain is L1 and the length of the second golden chain is L2, linking these 2 chains will take David (L1+L2) dollars.
Since David wants to save money, he wants to know what the cheapest way to link all chains into one is.
Then, what is the cheapest way to link all chains? Only follow an easy rule. Pick up the shortest 2 chains, and link them together until there is only one chain are left. Just like the Huffman tree and Huffman code.
The first line in the input file is an integer T( ≤ 20) followed by T test cases. Each test case describes the chains David purchases. The description consists of two parts:
1. The first part is an integer N( 1 ≤ N ≤ 40,000) describing the number of chains he purchases in a line.
2. There are N integers L1, L2, ..., LN, describing the length of N chains in N lines for each of them.
For each test case, output the cheapest cost that David need to spend in a single line.