import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();
        while(T--!=0){
            int n=sc.nextInt();
            int N=300010;
            long s[]=new long[N]; 
            long a[]=new long[N]; // 操作后的数组
            boolean st[]=new boolean[N]; // 两步跳的判重
            long res=0;
            for(int i=1;i<=n;i++){
                s[i]=sc.nextInt();
                s[i]+=s[i-1]; // 前缀和数组
            }
            long std=s[0],ed=s[n]; // 两个不可变的值
            if(std>ed){ //小在前，大在后
                std=s[n];
                ed=s[0];
            }
            int s0=0,sn=0; //排序后的两个值下标

            Arrays.sort(s,0,n+1);  
            for(int i=0;i<=n;i++){ 
                if(std==s[i]) s0=i; // 查找下标
                if(ed==s[i]) sn=i; 
            }

            int l=0,r=n; //存操作后的数组下标的头尾，否则一步一步来 不易操作 从sn跳到最大值 
            /*
            这三步也可以按步骤来，s0到sn循环，然后sn两步两步跳到最大值 --> 最大值跳到sn
            */
            for(int i=(int)s0;i>=0;i-=2){  // s0两步两步跳到最小值 
                st[i]=true;
                a[l++]=s[i];
            }
            for(int i=(int)sn;i<=n;i+=2){
                st[i]=true;  //最后是 sn 两步两步跳到最大值
                a[r--]=s[i];
            }
            for(int i=0;i<=n;i++){
                if(!st[i]) a[l++]=s[i]; //然后是最小值跳回到s0 --> s0走到sn --> sn跳回到最大值
            }
            for(int i=1;i<=n;i++) res=Math.max(res,Math.abs(a[i]-a[i-1])); // 间隔差最大值
            System.out.println(res);
        }
    }
}