NEO

Statement

You are given array a with n integer elements. You can divide it into several parts (may be 1), each part consisting of consecutive elements. The NEO value in that case is computed by: Sum of value of each part. Value of a part is sum all elements in this part multiple by its length.

Example: We have array: [ 2 3 -2 1 ]. If we divide it, so it looks like: [2 3] [-2 1], then NEO = (2 + 3) * 2 + (-2 + 1) * 2 = 10 - 2 = 8.

Because there are many ways to divide an array into several part, we can get many different NEO values. Your task is find the NEO with maximum value.

Input

First line: T (number of test cases, T ≤ 10) For each of testcase:
  • First line: n (1 ≤ n ≤ 105)
  • Second line: a[1], a[2], ..., a[n] (-106 ≤ a[i] ≤ 106)

Output

For each test case, print the maximum NEO value.

Example input
1
4
1 2 -4 1
	
Example output
3
	
Time and memory limit:

  • 4 seconds
  • 256MB

Problem source: SPOJ