#include
using namespace std;
int k(int a[],int n);
int max(int a[],int n)
{
int max_k=k(a,n);
int max_wrap=0,i;
for(i=0;i<n;i++)
{
max_wrap += a[i];
a[i] = -a[i];
}
max_wrap = max_wrap + k(a,n);
return (max_wrap>max_k)?max_wrap:max_k;
}
int k(int a[],int n)
{
int cs=0,ms=0;
for(int i=0;i<n;i++)
{
cs=cs+a[i];
if(cs<0)
{
cs=0;
}
if(ms<cs)
{
ms=cs;
}
}
return ms;
}
int main()
{
int t;
cin>>t;
for(int j=0;j<t;j++)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<endl;
max(a,n);
}
return 0;
}
