#include <iostream>
using namespace std;
#define N 1000000

int a[N+2];

int main() {
    int t; cin>>t;
    while(t--) {
        int n;
        cin>>n;

        for(int i = 0; i < n; ++i) cin>>a[i];
        int cur_mx = 0, mx = 0, s = 0;
        for(int i =0 ; i < n; ++i) {
            if(cur_mx + a[i] >=0) {
                cur_mx += a[i];
            } else{
                cur_mx = 0;
            }
            if(cur_mx > mx) mx = cur_mx;
            s += a[i];
        }

        
        int cur_mn = 0, mn = 0;
        for(int i = 0; i < n; ++i) {
            if(cur_mn + a[i] < 0) {
                cur_mn += a[i];
            } else {
                cur_mn = 0;
            }
            if(cur_mn < mn) mn = cur_mn;
        }
        cout << max(mx, s - mn) << endl;

    }
    return 0;
}