#include<iostream>
using namespace std;
int T,n,a[1005],dpl[1005],dpr[1005],ans;
void solve(){
	ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	int l=1,r=n,ll,rr;
	bool flag=true;
	while(l<=r){
		if(l==r){
			if(flag){
				ans+=a[l]; 
			}
			break;
		}
		dpr[l-1]=dpl[r+1]=0;
		ll=r,rr=l;
		for(int i=l;i<=r;i++){
			if(dpr[i-1]<0){
				rr=i;
			}
			dpr[i]=max(0,dpr[i-1])+a[i];
		}
		for(int i=r;i>=l;i--){
			if(dpl[i+1]<0){
				ll=i;
			}
			dpl[i]=max(0,dpl[i+1])+a[i];
		}
		if(flag){
			ans+=max(dpl[l],dpr[r]);
		}		
		if(dpr[r]>=dpl[l]){
			r=rr-1;
		}else{
			ans+=dpl[l];
			l=ll+1;
		}
		flag=!flag;
	}
	cout<<ans<<"\n";	
	return;
}
int main(){
	scanf("%d",&T);
	while(T--){
		solve();
	}
	return 0;
}