## NEO2 - NEO

Given array with n integer elements. We divide it into several part (may be 1), each part is a consecutive of 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 look likes: [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, so we can get many of NEO value. Your task is find the NEO with maximum value.

### Input

First line: T (number of test case, T <= 10)

For each of testcase:

+ First line: n (1 <= n <= 10^5)

+ Second line: a[1], a[2], ..., a[n] (-10^6 <= a[i] <= 10^6)

### Output

Each testcase print the

### Example

Input:1

4 1 2 -4 1

Output:3

Added by: | Gầy :)) |

Date: | 2017-06-14 |

Time limit: | 2s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |