Merging Files

The novelist Kim Daejeon writes a novel in several chapters and stores each chapter in a separate file. Once every chapter is written, the files are merged into a single file that holds the finished novel. The merging works like this. Two files are merged into one temporary file, and temporary files or original files are again merged two at a time. The two files being merged must hold chapters that run consecutively, and in the end only one file is left. The cost of merging two files is the sum of the two file sizes.

For example, let C1, C2, C3, C4 be files holding four consecutive 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 for that order 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, for a total of $70+80+150=300$.

Given the size of the file holding each chapter, write a program that computes the minimum total cost of merging the files into one.

The program reads its input data from standard input. The first line holds the number of test data, $T$.

Each test datum is given on two lines. The first line holds a positive integer $K$ ($3 \le K \le 500$), the number of chapters in the novel. The second line holds $K$ positive integers separated by spaces, the sizes of the files holding chapter 1 through chapter $K$. A file size does not exceed 10,000.

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