陪小屁孩买东西

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

今天,WAVwind陪小屁孩去苏果超市买东西,可是,付账的时候人实在太多了,而且大家都买了好多好多东西,一个人付账就要好长时间。小屁孩就买了一盒饼干,WAVwind拿着那盒饼干站在队伍末尾,WAVwind心里就想啊:让我先付账多好啊,也浪费不了后面人的多少时间,可能半分钟就搞定了。

假设已知队伍的人数为N,且每个人付账需要的时间也确定了为Ai,现在呢,WAVwind请你计算一下,怎样排队可以使得N个人全部都付完帐后大家总的等待时间最短。

Input

一个整数CASE,表示测试样例的个数。对于每组数据,输入一个整数N(1<=N<=1000),表示总排队的人数,接着N个整数分别表示每个人付账需要的时间。(1<=Ai<=100)

Output

要求输出最少的总等待时间。 (自己付账时的等待时间也算入其中)

Sample Input

1
3
4 7 1

Sample Output

18

Hint

Source


提交代码