n个男孩去相亲，排成一队上场。大家都不想等，排队越靠后越愤怒。每人的耐心不同，用D表示火气，设男孩i的火气是Di，他排在第k个时，愤怒值是(k−1)∗Di。   导演不想看到会场气氛紧张。他安排了一个黑屋，可以调整这排男孩上场的顺序，屋子很狭长，先进去的男孩最后出来（黑屋就是一个堆栈）。例如，当男孩A排到时，如果他后面的男孩B火气更大，就把A送进黑屋，让B先上场。一般情况下，那些火气小的男孩要多等等，让火气大的占便宜。不过，零脾气的你也不一定吃亏，如果你原本排在倒数第二个，而最后一个男孩脾气最坏，导演为了让这个刺头第一个上场，把其他人全赶进了黑屋，结果你就排在了黑屋的第1名，第二个上场相亲了。   注意，每个男孩都要进出黑屋。   对所有男孩的愤怒值求和，求所有可能情况的最小和。

第一行包含一个整数T(0<T<=100)，即测试用例的数量。对于第2至T+1行，第一个数字是n（0 <n <= 200），后面有n个整数，表示男孩的火气值D1-Dn（0 <= Di <= 100）。每一行的数字之间用空格隔开。

对每个用例，输出最小愤怒值之和。

动规专题