#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using _TYPE = int;
typedef tree< _TYPE, null_type, less< _TYPE >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template<typename T, typename V>
void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template<typename T>
void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
template<typename T>
void print_array(T *a, int size) {
    int f = 0;
    cerr << '{';
    for (T *i = a; i != (a + size); i++) cerr << (f++ ? "," : ""), __print(*i);
    cerr << "}" << endl;
}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int main() {
    IO;
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> inp;
        for(int i = 0; i < n; i++) {
            int a;
            cin >> a;
            inp.push_back(a);
        }
        inp.push_back(0);
        ll ans = 0;
        for(int i = 0; i <= n; i++) {
            int low = inp[i];
            while(i <= n && inp[i + 1] && ((inp[i] ^ inp[i + 1]) >= 0)) {
                low = max(low, inp[i + 1]);
                i++;
            }
            ans += low;
        }
        cout << ans << endl;
    }
    return 0;
}