#include <bits/stdc++.h>
using namespace std;
#define accelerate ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl "\n";
#define mod 1000000007
#define ll long long
#define PII pair<int,int>
#define INF 0x3f3f3f3f
const int N=1e6+10;
int n,m,k,x,y,T,ans;
ll a[N];
ll pre[N];
ll b[N];
bool vis[N];
int main(){
	accelerate;
	cin>>T;
	while(T--){
		cin>>n;
		pre[0]=0;
		memset(pre,0,sizeof(pre));
		for(int i=1;i<=n;i++){
			cin>>a[i];
			pre[i]=pre[i-1]+a[i];
		}
		ll s0=pre[0],sn=pre[n];
		if(s0>sn) swap(s0,sn);
		sort(pre,pre+n+1);
		int l=0,r=n;
		for(int i=0;i<=n;i++){
			if(pre[i]==s0){
				s0=i;
				break;
			}
		}
		for(int i=n;i>=0;i--){
			if(pre[i]==sn){
				sn=i;
				break;
			}
		}
		for(int i=s0;i>=0;i-=2){
			b[l++]=pre[i];
			vis[i]=1;
		}
		for(int i=sn;i<=n;i+=2){
			b[r--]=pre[i];
			vis[i]=1;
		}
		for(int i=0;i<=n;i++){
			if(!vis[i]){
				b[l++]=pre[i];
			}
		}
		ll ans=0;
		for(int i=1;i<=n;i++){
			ans=max(ans,abs(b[i]-b[i-1]));
		}
		cout<<ans<<endl;
		memset(vis,0,sizeof(vis));
	}
	return  0;
}