Maximum Subarray Sum

Given an integer array $X$ of size $N$, find the maximum sum of any contiguous subarray. That is, compute $\max_{1 \le i \le j \le N} (X[i] + \cdots + X[j])$.

The first line contains the number of test cases $T$. Each test case has one line with N$$(1 \le N \le 1000), then a line with $N$ integers separated by spaces, each with absolute value less than $1000$.

For each test case, print the maximum subarray sum on its own line.