有 $n$ 个变形虫排成一个圆圈。它们被编号为 $1$ 到 $n$。对于每个 $i$，变形虫 $i$ 和 $i+1$ 是邻居。此外，变形虫 $1$ 和 $n$ 也是邻居。第 $i$ 个变形虫的体积为 $a_i$。

两个相邻的变形虫可以合并。合并后，这两个变形虫消失，并在它们的位置出现一个新的变形虫。新变形虫的体积等于这两个变形虫体积之和。该操作的代价等于这两个变形虫体积的最小值。变形虫将持续合并，直到只剩下一个变形虫为止。

求直到只剩下一个变形虫时，所有操作的总代价的最小值。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)，表示变形虫的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示变形虫的体积。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示直到只剩下一个变形虫时，所有操作的总代价的最小值。

样例

输入 1

3
3
1 1 1
4
0 1 0 2
2
100 42

输出 1

2
1
42