#include<bits/stdc++.h>
using namespace std;
/*void func(int **arr, int row, int colum) {
for (int i = 0; i < colum; ) {
if (i % 2 == 0) {
for (int j = 0; j < row ; j++) {
cout << arr[j][i] << ‘,’ << " ";
}
}
else {
for (int j = 0; j < row; j++) {
cout << arr[row - j - 1][i] << ‘,’ << " ";
}
}
i++;
// for
}
}
void target_pairS(int *a, int n, int pair) {
// unordered_set ss;
unordered_map<int, int> m;
for (int i = 0; i < n; i++) {
m[a[i]]++;
}
for (int i = 0; i < n; i++) {
cout << "inside";
if (a[i] < pair) {
if (m.find(pair - a[i]) != m.end() && m[a[i]] > 0 && m[pair - a[i]] > 0) {
cout << a[i] << " and " << pair - a[i];
m[a[i]]--;
m[ pair - a[i]]--;
}
}
}
}
void printTargetSumTriplet(int a,int n){
sort(a,a+n);
for(int i=0;i<n-2;i++){
for(int j=i+1;j<n;j++){
if(a[i]+)
}
}
}/
/*void swap(int *a, int *b) {
int *t = a;
a = b;
b = t;
}
void imagerotation(vector<vector> a, int n , int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == j) {
if (j + 1 <= m - 1 && i + 1 <= n - 1) {
swap(a[i][j - 1], a[i][j + 1]);
}
if (i + 1 != n && j - 1 >= 0 && i - 1 >= 0 && j + 1 != n) {
swap(a[i - 1][j], a[i][j - 1]);
swap(a[i - 1][j + 1], a[i + 1][j - 1]);
swap(a[i][j + 1], a[i + 1][j]);
}
}
else {
}
}
}
int j;
for (int i = 0; i < n; i++) {
for (int k = 0, j = n - 1; k <= j; j--, k++) {
swap(a[i][k], a[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << a[i][j] << " ";
}
cout << "\n";
}
}*/
/*int rainwater(vector a) {
vector ll(a.size(), -1);
vector rr(a.size(), -1);
int lm = a[0];
ll[0] = a[0];
for (int i = 0; i < a.size(); i++) {
if (a[i] > lm) {
lm = a[i];
ll[i] = lm;
}
else {
ll[i] = lm;
}
}
int rm = a[a.size() - 1];
rr[a.size() - 1] = rm;
for (int i = a.size() - 1; i >= 0; i–) {
if (a[i] > rm) {
rm = a[i];
rr[i] = rm;
}
else {
rr[i] = rm;
}
}
cout << “cc” << “\n”;
int w = 0;
for (int i = 0; i < a.size(); i++) {
if (ll[i] == rr[i]) {
w += ll[i] - a[i];
}
if (ll[i] < rr[i]) {
w += ll[i] - a[i];
}
if (rr[i] < ll[i]) {
w += rr[i] - a[i];
}
}
return w;
}*/
/int maxSumSub(vector a) {
int cs = 0;
int ms = -1;
for (int i = 0; i < a.size(); i++) {
cs = cs + a[i];
if (ms < cs) {
ms = cs;
}
if(cs<0){
cs=0;
ms=ms;
}
}
}/
/int kadane(int a[], int n)
{
int max_so_far = 0, max_ending_here = 0;
int i;
for (i = 0; i < n; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
int maxcc(int a[], int n) {
int max_so_far = 0, max_ending_here = 0;
int i;
for (i = 0; i < n; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
// return max_so_far;
// int max_so_far = 0, max_ending_here = 0;
// int i;
for (i = 0; i < n - 1; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
// return res;
}/
int maxCirSum(vector a) {
int cs = 0;
int ms = 0;
for (auto it = a.begin(); it != a.end(); it++) {
cs += *it;
//cout << “cs” << cs << “\n”;
if (ms < cs) {
ms = cs;
}
if (cs < 0) {
cs = 0;
ms = ms;
}
}
int res1=ms;
int sumarr = 0;
for (int i = 0; i < a.size(); i++) {
sumarr += a[i];
}
for (int i = 0; i < a.size(); i++) {
a[i] = -a[i];
}
int mcx = 0;
int mmx = 0;
for (auto it = 0; it <= a.size(); it++) {
mcx += a[it];
if (mmx < mcx) {
mmx = mcx;
}
if (mcx < 0) {
mcx = 0;
mmx = mmx;
}
}
// mmx = -mmx;
if (res1 > (sumarr + (mmx)))return res1;
else return sumarr + mmx;
}
int main()
{
/* vector<vector> a{{1, 2}, {4, 5}};
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < a[i].size(); j++) {
cout << a[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
// cin >> target;
imagerotation(a, a.size(), a[0].size());
*/ // (arr, row, colum);
// vector<int> a{0 , 2, 1, 3, 0, 1, 2, 1, 2, 1};
// cout << rainwater(a);
int n;
cin >> n;
while (n--) {
int m;
cin >> m;
// cout << "enter1" << "\n";
vector<int> a;
//int a[m];
// cout << "enter2" << "\n";
int s = 0;
for (int i = 0; i < m; i++) {
cin >>s ;
a.push_back(s);
//cin >> a[i];
}
// cout << "enter23" << "\n";
cout << maxCirSum(a) << "\n";
}
return 0;
}