题目描述

有 $n$ 堆石子排成一行，每个石子的重量分别为 $a_1,a_2,\cdots,a_n$，对于所有 $i(1 \le i \lt n)$，我们认为石子 $i$ 和 $i+1$ 相邻。

一次操作可以合并相邻两堆石子，合并的代价是两堆石子重量的较小值。合并后，这两堆石子会消失，且会在它们的位置出现一堆新的石子，其重量为这两堆石子重量的和。

形式化的说，若有石子序列 $a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n$，对第 $i$ 和第 $i+1$ 堆石子合并，代价为 $\min\{a_i,a_{i+1}\}$，新的石子序列为 $a_1,a_2,\cdots,a_i+a_{i+1},\cdots,a_n$。

你想要把所有石子合并成一堆，求花费的最小总代价。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示石子的重量。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例

样例输入

2
3
1 1 1
4
0 0 0 1

样例输出

2
0

对于第一组数据：先合并前两颗石子，新的序列为 $\{2,1\}$，代价为 $1$；然后将这两颗石子合并，代价为 $1$，总代价为 $1+1=2$。

数据范围与约定

对于所有数据，有：

• $1 \le T \le 5$
• $2 \le n \le 10^5$
• $0 \le a_i \le 10^9$