227. 煉金術

煉金術

煉金術的一個非常重要的原則就是等價交換。今天你有兩個物品$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$。

輸出說明

對於每筆測資，輸出最少需要多少代價。

範例輸入

2 3 1 2 3 5 1 4 2 5 3

範例輸出

9 35

提示

第一筆測資中，只有兩種合成的方法：

• 先合成1、2，產生出價值為3 的物品，再合成3、3，需要(1+2)+(3+3)=9單位的代價
• 先合成2、3，產生出價值為5 的物品，再合成1、5，需要(2+3)+(1+5)=11單位的代價

最小值為9。

Judge Setting

run-time limit: 70 ms
memory limit: 512000 byte
測資數量: 0