#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int t,n;
cin>>t;
while(t--){
vector<long long int> meh;
long long int temp,sol;
cin>>n;vector<long long int> arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
meh.push_back(arr[0]);
long long int msf = 0 > arr[0]? 0:arr[0];
for(int i=1;i<n;i++){
temp = meh[0];
for(int j=0;j<meh.size();j++){
meh[j] += arr[i];
if(msf < meh[j])
msf = meh[j];
if(meh[j] < 0)
meh[j] = 0;
}
if(arr[i] < 0)
meh.push_back(temp);
}
temp = *std::max_element(meh.begin(),meh.end());
sol = temp>msf?temp:msf;
if(temp == 0){
sol = *std::max_element(arr.begin(),arr.end());
}
cout<<sol<<endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CglpbnQgdCxuOwoJY2luPj50OwoJd2hpbGUodC0tKXsKCQl2ZWN0b3I8bG9uZyBsb25nIGludD4gbWVoOwoJCWxvbmcgbG9uZyBpbnQgdGVtcCxzb2w7CgkJY2luPj5uO3ZlY3Rvcjxsb25nIGxvbmcgaW50PiBhcnIobik7CgkJCgkJZm9yKGludCBpPTA7aTxuO2krKyl7CgkJCWNpbj4+YXJyW2ldOwoJCX0KCQkKCQltZWgucHVzaF9iYWNrKGFyclswXSk7CgkJbG9uZyBsb25nIGludCBtc2YgPSAwID4gYXJyWzBdPyAwOmFyclswXTsKCQkKCQlmb3IoaW50IGk9MTtpPG47aSsrKXsKCQkJdGVtcCA9IG1laFswXTsKCQkJCgkJCWZvcihpbnQgaj0wO2o8bWVoLnNpemUoKTtqKyspewoKCQkJCW1laFtqXSArPSBhcnJbaV07CgkJCQlpZihtc2YgPCBtZWhbal0pCgkJCQkJbXNmID0gbWVoW2pdOwoJCQkJaWYobWVoW2pdIDwgMCkKCQkJCQltZWhbal0gPSAwOwoJCQl9CgkJCQlpZihhcnJbaV0gPCAwKQoJCQkJCW1laC5wdXNoX2JhY2sodGVtcCk7CgkJfQoJCQoJCXRlbXAgPSAgKnN0ZDo6bWF4X2VsZW1lbnQobWVoLmJlZ2luKCksbWVoLmVuZCgpKTsKCQlzb2wgPSB0ZW1wPm1zZj90ZW1wOm1zZjsKCQkKCQlpZih0ZW1wID09IDApewoJCQlzb2wgPSAqc3RkOjptYXhfZWxlbWVudChhcnIuYmVnaW4oKSxhcnIuZW5kKCkpOwoJCX0KCQkKCQljb3V0PDxzb2w8PGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==