Merging Files 3

The novelist Kim Daejeon writes a novel as several chapters and keeps each chapter in its own file. Once every chapter is written, the files are merged into a single file that holds the finished novel. A merge always takes two files and turns them into one, and a temporary file produced this way can be merged again with another file. Repeating this leaves exactly one file at the end.

The cost of merging two files is the sum of the two file sizes. Given the size of the file for each chapter, compute the minimum total cost of merging all of them into one file.

For example, let C1, C2, C3, C4 be the files of four chapters with sizes 40, 30, 30, 50. Merging C2 and C3 into a temporary file X1 costs 60. Merging C1 and X1 into X2 then costs 100, and merging X2 with C4 costs 150. The total cost is 60 + 100 + 150 = 310. A different order costs less. Merge C1 and C2 into Y1, merge C3 and C4 into Y2, then merge Y1 and Y2: the total cost is 70 + 80 + 150 = 300.

Input arrives on standard input. The first line holds the number of test data $T$. Each test datum takes two lines. The first line holds a positive integer $K$ ($3 \le K \le 1{,}000{,}000$), the number of chapters in the novel. The second line holds $K$ positive integers separated by spaces, the sizes of the files for chapters 1 through $K$. No file size exceeds $10{,}000$.

Write to standard output. For each test datum, print on exactly one line the minimum cost of merging every chapter into a single file.