Stone
题号：NC25576
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

有n堆石子排成一排，第i堆石子有a_i个石子。
每次，你可以选择任意相邻的两堆石子进行合并，合并后的石子数量为两堆石子的和，消耗的体力等价于两堆石子中石子数少的那个。
请问，将所有的石子合并成一堆，你所消耗的体力最小是多少？

输入描述:

第一行是一个整数，表示样例的个数。
每个样例的第一行是一个整数,表示石子堆的数量。
第二行是n个整数

输出描述:

每行输出一个样例的结果。
示例1

输入

复制 
2
2
1 2
1
1

输出

复制 
1
0

说明

巨大的输入，请使用C风格的输入。