#include
#include<limits.h>
using namespace std;
int reverkadene(int b[],int s)
{
for(int i=0;i<s;i++)
{
b[i]=-1*b[i];
}
int maxsf=b[0];
int maxhere=0;
for(int i=0;i<s;i++)
{
maxhere+=b[i];
if(maxhere<0)
maxhere=0;
maxsf=max(maxsf,maxhere);
}
return maxsf;
}
int kadane( int arr[],int N)
{ bool f=true;
for(int i=0;i<N;i++)
{
if(arr[i]>=0)
f=false;
}
int mini=INT_MAX;
int sum=0;
for(int i=0;i<N;i++)
{
sum+=arr[i];
mini=min(mini,arr[i]);
}
if(f==true)
return mini;
else
return sum+ reverkadene(arr,N);
}
int main() {
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<kadane(a,n)<<endl;
}
return 0;
}