Given an array, find the maximum subset sum of that array. A subset is a set of consecutive elements in the array.

Input

The first line of the input contains an integer t, denoting the number of test cases.

Each test case contains 2 lines. The first line consists of a number n, the number of elements in the array.

The second line consists of n numbers, the elements in the array.

All input fits in the integer size.

Output

Output a number for each test case, denoting the maximum subset sum of that array.

Example

Input:
2
4
1 -4 10 12
5
-1 5 6 -2 12

Sample Output
22
21

Explanation

22 and 21 are the maximum sums that can be obtained from the given array by adding consecutive numbers.