#include <bits/stdc++.h>
using namespace std;
 
int maxSubArray(vector<int>& nums) {
        int sum = nums[0];
        int result = nums[0];
 
        for(int i=1;i<nums.size(); i++)
        {
            sum = max(nums[i],sum+nums[i]);
            if(sum>result)
                result = sum;
        }
        return result;
    }
 
int main() {
	int t;
	cin>>t;
	while(t--)
	{
		int n;cin>>n;
		vector<int> nums;
		for(int i=0;i<=n;i++)
		{
			int x;
			cin>>x;
			nums.push_back(x);
		}
 
		cout<< maxSubArray(nums)<<"\n";
 
 
	}
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWF4U3ViQXJyYXkodmVjdG9yPGludD4mIG51bXMpIHsKICAgICAgICBpbnQgc3VtID0gbnVtc1swXTsKICAgICAgICBpbnQgcmVzdWx0ID0gbnVtc1swXTsKICAgICAgICAKICAgICAgICBmb3IoaW50IGk9MTtpPG51bXMuc2l6ZSgpOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBzdW0gPSBtYXgobnVtc1tpXSxzdW0rbnVtc1tpXSk7CiAgICAgICAgICAgIGlmKHN1bT5yZXN1bHQpCiAgICAgICAgICAgICAgICByZXN1bHQgPSBzdW07CiAgICAgICAgfQogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9CgppbnQgbWFpbigpIHsKCWludCB0OwoJY2luPj50OwoJd2hpbGUodC0tKQoJewoJCWludCBuO2Npbj4+bjsKCQl2ZWN0b3I8aW50PiBudW1zOwoJCWZvcihpbnQgaT0wO2k8PW47aSsrKQoJCXsKCQkJaW50IHg7CgkJCWNpbj4+eDsKCQkJbnVtcy5wdXNoX2JhY2soeCk7CgkJfQoJCQoJCWNvdXQ8PCBtYXhTdWJBcnJheShudW1zKTw8IlxuIjsKCQoJCQoJfQoJcmV0dXJuIDA7Cn0=

Mwo5Ci0yNCAwIDI4IDI4IDU1IC0zMSAtMjcgLTQ1IC0yNCAKMTAKNDAgNSAzOSA0NSAzMSAtNDQgNzMgLTE2IC0zMSAyNyAKNwo1NyAxOCAtMTQgMTcgMzEgMTYgLTE2IA==

3
9
-24 0 28 28 55 -31 -27 -45 -24 
10
40 5 39 45 31 -44 73 -16 -31 27 
7
57 18 -14 17 31 16 -16