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\)