Background

快要期中考试了，刘学习总是说“书上的内容才是最经典最有用的！”，刘学习决定在考前复习他的n门课的课本。

Description

刘学习有n门课的课本需要复习，并且这些书按照编号1～n的顺序从上往下放在了刘学习的桌子上。
第i门课的课本有一个难度值a[i]，刘学习的不快乐值与课本的难度相关，而刘学习需要按照一定的顺序复习这些课本，才能让自己更快乐。
刘学习是一个做事井井有条的人，因此他将按照如下规则复习。
1.拿桌子上一堆书中最上端的那本课本复习
2.将桌子最上端的一本课本放到一个长和宽恰好和课本完全相同的纸箱子中
3.从纸箱子中拿走纸箱子最上面的一本课本复习
因为刘学习会越学越累，因此对于编号为i的课，如果它是第k门被刘学习复习到的课，则他会让刘学习感受到(k-1)*a[i]的不快乐。
1～n门课所有课给刘学习感受到的不快乐总和即为刘学习最终的不快乐值。
请问如何复习才能让刘学习最快乐呢？(最小化不快乐值）
请输出最小的不快乐值。

Format

Input

第一行一个正整数T即数据组数
对于每组数据第一行一个正整数n表示n门课
接下来n行每行一个正整数a[i]即第i门课的难度值

Output

对于每组数据输出:
一行一个正整数ans，表示刘学习最小的不快乐值

Sample 1

Input

1
5
5
4
3
2
2

Output

24

Limitation

1s, 64MbKiB for each test case.

对于所有数据T<=100 a[i]<=100
对于30%的数据n<=5
对于60%的数据n<=20
对于80%的数据n<=50
对于100%的数据n<=100

Source

lyhlyhlyh