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+55 == 52