#include<stdio.h>
int head[51001],tail[51001],arr[51001],n;
int main()
{
	int max(int,int);
	int sum1(int);
	int sum2(int);
	int i,j,maxsum=0,max1=0,max2=0,m,count=0,mm=-20000,t;
	scanf("%d",&m);
	printf("\n");
	for(;m>0;m--)
	{
		count=0;
		maxsum=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&arr[i]);
		if(arr[i]>=0)
			count++;
	}
	if(count>=2)
	{
		if(arr[0]>0)
		head[0]=arr[0];
		else head[0]=0;
		if(arr[n-1]>0)
		tail[n-1]=arr[n-1];
		else tail[n-1]=0;

	for(i=1;i<n;i++)
	{
		head[i]=sum1(i);
	}
	for(i=n-2;i>0;i--)
	{
		tail[i]=sum2(i);
	}
	for(i=0;i<n;i++)
	{
		max1=0,max2=0;
		for(j=0;j<=i;j++)
		    max1=max(head[j],max1);
		for(j=n-1;j>i;j--)
			max2=max(tail[j],max2);
		maxsum=max(maxsum,max1+max2);
	
	}
	}
	else 
	{
		for(i=0;i<n;i++)
			if(arr[i]>mm)
			{
				mm=arr[i];
				t=i;
			}
	
			maxsum=maxsum+arr[t];
			mm=-20000;
			arr[t]=-20000;
			for(i=0;i<n;i++)
				if(arr[i]>mm)
				{
					mm=arr[i];
					t=i;
				}
				maxsum=maxsum+arr[t];
	}
	printf("%d\n",maxsum);
	if(m!=1)
		printf("\n");
	}
		return 0;
}
int max(int x,int y)
{
	if(x>y)
		return x;
	else return y;
}
int sum1(int m)
{
	int s=0,i;
	if(head[m-1]+arr[m]>0)
	return head[m-1]+arr[m];
	else return 0;
}
int sum2(int m)
{
	int s=0,i;
	if(tail[m+1]+arr[m]>0)
		return tail[m+1]+arr[m];
	else return 0;
}