#include
#include
using namespace std;
int main() {
int m;
cin>>m;
while(m–){
int n;
cin>>n;
int a[1000];
for(int i=0;i<n;i++){
cin>>a[i];
}
int cs,ms = 0;
for(int i=0;i<n;i++){
cs += a[i];
if(cs<0){
cs = 0;
}
ms = max(cs,ms);
}
int c2=0;
for(int i=0;i<n;i++){
c2+=a[i];
}
int mini =INT_MAX;
int cmin = INT_MAX;
for(int i=0;i<n;i++){
if(mini>0){
mini = a[i];
}
else{
mini += a[i];
}
cmin = min(mini,cmin);
}
int sum = c2 - cmin;
cout<<max(sum,ms);
}
return 0;
}