Background

电视节目You Are The One一直很受欢迎。为了满足仍然单身的男孩的需要，TJUT 自己举办演出。演出在小礼堂举行，所以吸引了很多男孩和女孩。现在有n个男孩报名了。一开始，n 男孩们排成一排，一个接一个地走到舞台上。

然而，导演知道，每一个男孩有不满值D，如果男孩是第k个去舞台，他的不满将是（k-1）*D，因为他必须等待（k-1）人。

幸运的是，小大厅里有一个黑暗的房间，所以导演可以暂时把男孩放进黑暗的房间，让后面的男孩在他面前上台。因为黑暗的房间很窄，第一次进入暗室的男孩必须最后离开。

导演想在暗室里改变男孩的顺序，所以不满意总值最低。你能帮他吗？

Format

Input

第一行包含单个整数 T，测试案例的数量。对于每个案例，第一行是 n （0 < n < = 100）

下一行是 n 整数 D1-Dn 表示男孩不满值 （0 <= di < = 100）

Output

对于每个测试案例，输出最少的不满意总值。

Samples

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

Case #1: 20
Case #2: 24

Limitation

1s, 1024KiB for each test case.