0 Judge
Code: 0
煉金術的一個非常重要的原則就是等價交換。今天你有兩個物品$A$、$B$,它們的價值分別是$x$,$y$,那要將$A$、$B$和成為另一個物品$C$所需要花費的代價就會是$x+y$,而且合成出來的物品$C$它的價值為$x+y$。
現在有$N$個物品要合成為一個價值超大的物品,顯然不管合成的順序如何,最終的價值都會相同(也就是$N$個物品的總和),但是過程消耗的代價卻不一樣,因此我們會希望代價越小越好。現在這$N$個物品被排成一排,而且只有相鄰的兩個物品可以進行合成,請問將這$N$個物品全部合成所需的最小代價是多少呢?
第一行為一個正整數$T(T \leq 10)$,表示共有$T$筆測資。 每筆測資第一行包含一個正整數$N$,表示共有$N$個物品要合成,$1 \leq N \leq 100$。 每筆測資第二行為$N$個正整數,表示排成一列之後的物品依序的價值$a_1,a_2,...,a_N$,$1 \leq a_i \leq 1000$。
對於每筆測資,輸出最少需要多少代價。
第一筆測資中,只有兩種合成的方法:
最小值為9。