import java.util.Scanner;
public class Main {
	public static int numTest;
	public static int n;
	
	public static int[] a = new int[50000];
	
	//e[i] = the maximum sum of sequence ending at i;
	public static long[] e = new long[50000];
	//b[i] = the maximum sum of sequence starting at i;
	public static long[] b = new long[50000];

	
	public static void main(String[] args) {

		Scanner sc = new Scanner( System.in );
		numTest = sc.nextInt();
			
		while( numTest > 0){
			
			n = sc.nextInt();
			for( int i = 0; i < n; i++)
				a[i] = sc.nextInt();
				
			//optimize
			e[0] = a[0];

			b[n-1] = a[n-1];
				
			//i for end;
			//j for beginning;
			int j;
			for( int i = 1; i < n; i++){
				j = n - 1 - i;
				
				e[i] = a[i];
				if ( e[i - 1] > 0)
					e[i] = a[i] + e[i-1];
				
				b[j] = a[j];
				if( b[j + 1] > 0)
					b[j] =  a[j] + b[j+1];
			}
			
			for( int i = n - 2; i >= 0; i--){
				if( b[i] < b[i + 1] )
					b[i] = b[ i + 1];
			}
				
				
			//find the maximum;
			long max = e[0] + b[1];
			for( int i = 1; i <= n-2; i++)
				if( max < e[i] + b[i+1])
					max = e[i] + b[i+1];
				
			System.out.println(max);
				
			--numTest;
		}//end while;
			
	}//end main;

}//end class;