测试数据来自 system/3067

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　相亲节目《非诚勿扰》的现场有 \(n\) 名帅哥，他们排成一队上场。每人的耐心不同，用 \(w_i\) 表示队伍中第 \(i\) 位帅哥的火气大小，因为他排在队伍的第 \(i\) 个，因此其愤怒值是 \((i−1)∗w_i\) ，那么初始队列的总愤怒值就是：\(0+w_1 + 2*w_2 + ... + (n-1)*w_n\)。

　　节目导演不想看到会场气氛过分紧张。他安排了一个栈，可以调整帅哥的上场的顺序，先进栈的帅哥最后出来。例如，当帅哥 \(P\) 排到时，如果他后面的帅哥 \(Q\) 火气更大，就把 \(P\) 送进栈，让 \(Q\) 先上场。一般情况下，那些火气小的帅哥要多等等，让火气大的占便宜。不过，零脾气的你也不一定吃亏，如果你原本排在倒数第二个，而最后一个帅哥脾气最坏，导演为了让这个刺头第一个上场，把其他人全赶进了栈，结果你就排在了栈的第 1 名，第二个上场相亲了。注意，每个帅哥都必须进栈和出栈一次。

　　请你帮导演算一算，该怎样调节帅哥的商场顺序。才能使得总愤怒值最小。

【输入格式】

　　第一行包含一个整数 \(T\)，即数据组数。对于每组数据，只有一行，这一行的第一个数是 \(n\)，后面接着的 \(n\) 个数是 \(w_1..w_n\)，表示初始队伍中第 \(i\) 个帅哥的火气值\(（0 ≤ wi ≤ 100）\)。

【输出格式】

　　对每组数据，输出最小愤怒值之和。

【输入输出样例】

　Input

2
5 1 2 3 4 5
5 5 4 3 2 2

　Output

20
24

【数据限制】

　　100%的数据满足：\(1≤T≤50\)，\(1≤n≤100\)，\(0 ≤ wi ≤ 100\)。

【来源】

　　Mr.he