题目描述

由于资金链断裂加上长期管理不善，幻想乡的知名共享单车大厂OGO陷入了破产危机，要求退押金的妖怪排成了一条长龙。由于裁员之后OGO只剩下了一个前台服务人员，因此前台接待客户的效率奇低，排在后面的妖怪们大吵大闹，严重影响了幻想乡的乡容和秩序。为了让这场闹剧尽可能结束，城管博丽灵梦决定介入退押金大队的管理和疏导工作。

由于OGO长期用灰色手段收集用户数据，因此对于退押金大队的每个妖怪，他们都可以根据其性格和行为习惯预测出这名用户要在前台滞留多长时间。设队伍里共有\(N\)个妖怪，队伍里从前往后第\(k\)个妖怪办理退押金手续的时间为\(t_k\)，\(k=1,2 \cdots N\)。若忽略其他的时间开销，那么可以认为第\(k\)个妖怪在队伍里等待的总时间是\(\sum_{i=1}^{k-1} t_i\)。灵梦想要调整队伍的顺序，从而使\(N\)名妖怪等待的时间之和尽可能小，于是她要求OGO将前台迁移到另一个地方，然后组织妖怪们排成新的队伍。

设新的队伍一开始为空，然后每次从原队伍中指定一个妖怪，让他排到新队伍的末尾，直到所有妖怪都迁移到新队伍为止。由于场地限制，每次只能在原队伍里剩下的妖怪中，指定最前边或最后边的一个。灵梦想知道，在队伍重新调整之后，\(N\)名妖怪的等待时间之和最多可以减少多少。队伍迁移本身花费的时间忽略不计（你可以假设妖怪们都会瞬移）。

I/O格式

输入

输入第一行是一个正整数\(T\)，表示测试数据组数。之后每组数据：
第一行是一个正整数\(N\)；
第二行是\(N\)个正整数\(t_1, t_2 \cdots t_N\)。

输出

输出一个非负整数表示答案。

样例

输入

2
5
5 10 25 10 15
10
5 2 10 3 9 8 1 4 7 6

输出

20
31

样例说明

对于第一组样例，原来的队伍中5名妖怪等待的时间依次为0,5,15,40,60，所以等待时间之和为\(0+5+15+40+60=120\)；按照“前、前、后、后、前”的顺序将5名妖怪迁移到新队伍，则在新队伍中，5名妖怪的等待时间依次为0,5,15,30,50，等待时间之和为\(0+5+15+30+50=100\)，比原来减少了20。

数据规模及约定

40%的数据：\(T \le 10, \quad N \le 16\)；
100%的数据：\(T \le 10, \quad N \le 2500, \quad t_i \le 10^9\)。

限制

1s, 64MB