排队打饭

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一天中午,有N个学生来到食堂买饭,他们需要排成了一个一字队伍并按顺序打饭,现在已经知道了每个人买饭的时间,现在食堂的管理员希望知道他们按照怎样的顺序买饭能够使得所有人等待的时间总和最小(每个人等待的时间 = 排在他前面的人的打饭时间和+自己打饭的时间)。

Input

 输入的第一行包含一个整数TT30)表示数据组数,每组数据包括两行,第一行为一个整数N表示人数,第二行为N个整数表示每个人买饭所需要的时间,所有整数均不超过100

Output

 每组数据输出一行,包括一个整数,表示所有人等待时间总和的最小值。

Sample Input

2
5
1 2 3 4 5
5
45 10 48 37 9

Sample Output

35
334

Hint

 

Source