For array \(A[]\) of \(N\) integers we call a function \(f_A = \sum_{i=1}^{N} i * A_i\)
Given array of \(N\) integers and in one move you can select a position and delete the array element. Then all elements to the right are shifted to the left by \(1\) position. For example, given array is \([5, 9, 15, 25, 15, 9]\), if you delete \(A_2\) then the array will be \([5, 15, 25, 15, 9]\) and then if you delete \(A_2\) the array will be \([5, 25, 15, 9]\).
Find the maximum value of \(f_A\) of modified array by performing the above move any number of times (possibly \(0\)).

Input format

• The first line contains \(T\) denoting the number of test cases. The description of each test case is as follows.
  • The first line contains an integer \(N\) denoting the number of array elements.
  • The next line contains \(N\) space-separated integers.

Output format

For each test case, print the answer in a new line.

Constraints

\(1 \leq T \leq 10\)

\(1 \leq N \leq 10^3\)

\(-10^9 \leq A_i \leq 10^9\)