Little piglet is fond of chocolates. Once she bought a box of chocolate which was open from both the ends. There were N chocolates inside the box and there was a different satisfaction factor associated with each of them. Shopkeeper told piglet that satisfaction factor of each chocolate will increase day by day. In simple words suppose the satisfaction factor of a particular chocolate is S on the day piglet purchased the box, and if she eats that chocolate after D days then the amount of satisfaction she’ll get from that chocolate is D*S. Piglet decided to eat one chocolate a day. Every day she will have two choices, either she can pull out a chocolate from left end or from the right end. She wants to choose the chocolates in such a way so as to maximize the total satisfaction of the box. She will tell you the current satisfaction factor of each chocolate in the form of an array C where C[i] is the satisfaction factor of ith chocolate. Write a code to find out the total satisfaction that she can get from this box.

Input

First line of input contains a number T i.e. the number of test cases. Each test case contains 2 lines. First lines contains a number N i.e. the number f chocolates in each box. Second line contains N space separated numbers denoting satisfaction factor associated with each chocolate.

Output

Your code should print T lines each having one numbers, i.e. the total satisfaction piglet will get from that chocolate box.

Constraints-

1<=T<=101

1<=N<=1000

1<=C[i]<=1000

Time limit-

2 second

Sample Input

1

5

1 5 3 2 4

Sample Output

52

Explanation

Piglet will choose chocolates in following order-

C[0]*1+C[4] 2+C[3]3+C[2]4+C[1]5 == 11+42+23+34+5*5 == 52