Maximum Healing Effectiveness

You are given multiple test cases. For each test case, a hero can collect healing points from a sequence of potions. However, some potions have negative healing effects. Your task is to help the hero choose a contiguous subarray of potions such that the sum of healing effects is maximized.

Formally, given an array \(a_1, a_2, \dots, a_n\) (which may contain negative values), find the maximum sum obtainable by summing a contiguous subarray. This is a classical application of Kadane's algorithm. The answer for each test case is the maximum possible sum.

Input/Output: Your solution should read the input from stdin and print the output to stdout. Each test case's answer should be printed on a new line.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each test case consists of two lines:

• The first line contains an integer \(N\) which is the number of potions.
• The second line contains \(N\) space-separated integers representing the healing effectiveness of each potion.

outputFormat

For each test case, output a single integer representing the maximum healing effectiveness that can be obtained by choosing a contiguous subarray. Each answer should be printed on its own line.

## sample

2
5
-1 2 3 -4 5
4
1 2 3 4

6
10

</p>