Maximum Magic Power

You are given T test cases. In each test case, you are provided with an integer N representing the number of fruits, and an array of N integers that denote the magic power of each fruit. Your task is to determine the maximum sum of magic power that can be gathered from a contiguous segment of fruits.

This problem is a classic application of Kadane's algorithm. In mathematical terms, for an array \(a_1, a_2, \dots, a_N\), you need to compute the value:

$$ \max_{1 \leq i \leq j \leq N} \sum_{k=i}^{j} a_k $$

Print the result for each test case on a separate line.

inputFormat

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

• The first line contains a single integer N — the number of fruits.
• The second line contains N space-separated integers representing the magic power values of the fruits.

outputFormat

For each test case, output the maximum contiguous subarray sum (i.e., the maximum magic power that can be gathered) on a new line.

## sample

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

5
7
15

</p>