Problem Statement:

Given an array of integers, find the maximum sum of a subarray of the array. A subarray is any continguous segment of the given array (can also be of length 0). Sum of a subarray is the sum of all the elements present in the subarray.

Input: First line of input contains the number of test cases, T. First line of each test case contains number of elements in the array, N. Next line contains the N space seperated integers, the elements of the array.

Output: T lines with a single interger in each line, denoting the maximum subarray sum of each.

Constrains: 1 <= T <= 100 1 <= N <= 10000 -1000 <= a[i] <= 1000

Subtasks:

Subtask#1 (5 points): 1 <= N <= 100

Subtask#2 (5 points): Original Constrains.

Sample input:

2 7 -5 6 7 1 4 -8 16 8 -2 -5 6 -2 -3 1 5 -6

Sample Output:

26 7

Explaination:

For the first testcase the required subarray is from 2nd element to 7th element (6 + 7 + 1 + 4 -8 + 16 = 26) For the second testcase the required subarray is from 3nd element to 7th element (6 -2 -3 + 1 + 5 = 7) This is the maximum sum possible.