#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200001

int t, n, ind, flag, ans, res, tmp;
int a[MAXN], b[MAXN], sum[MAXN];
vector<int> vec;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;
    while (t--){
        vec.clear();
        ans = 0;
        cin >> n;
        for (int i(1); i<=n; ++i) cin >> a[i];

        flag = n+1;
        for (int i(1); i<=n; ++i){
            cin >> a[i];
            if (a[i] <= 0){
                vec.push_back(a[i]);
                if (flag == n+1) flag = i;
            }else if (flag ^ (n+1)) ans += a[i];
        }
        --flag;

        ind = 0;
        for (int i(1); i<=n; ++i){
            if (a[i] > 0) b[++ind] = a[i];
        }
        ++ind;
        for (int i(ind); i<=n; ++i) b[i] = vec[i-ind];
        for (int i(1); i<=n; ++i) sum[i] = sum[i-1] + b[i];

        res = 0;
        for (int i(1); i<flag; ++i) res = max(res, sum[flag]-sum[i]-b[i]);
        ans += res;

        tmp = flag = 0;
        for (int i(n); i>=1; --i){
            if (a[i] > 0) flag = 1;
            else if (flag) ans -= a[i];
            else ++tmp;
        }
        ind = n+1;
        for (int i(n); i>=1; --i){
            if (a[i] <= 0){
                if (!tmp) break;
                ind = i;
                --tmp;
            }
        }
        ++ind;

        res = 0;
        for (int i(n); i>ind; --i) res = max(res, -(sum[i]-sum[ind-1])+b[i]);
        cout << ans + res << '\n';
    }

    return 0;
}