Maximum Subarray Sum

Problem Statement:

Given an array of integers, your task is to find the maximum sum of any contiguous subarray. For an array \(a_1, a_2, \dots, a_N\), the maximum subarray sum is defined as:

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

You are given \(T\) test cases. For each test case, you will be given an integer \(N\) and a list of \(N\) integers representing the elements of the array. Your program should compute and output the maximum subarray sum for each test case on a new line.

This problem can be efficiently solved using Kadane's algorithm.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer \(T\), the number of test cases.
• For each test case, the first line contains an integer \(N\) representing the number of elements in the array.
• The second line contains \(N\) space-separated integers.

outputFormat

For each test case, output a single line containing the maximum sum of any contiguous subarray.

The output should be written to standard output (stdout).

## sample

1
1
5

5

</p>