#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//////// 常用宏
#define F(n) for(int i=1;i<=n;++i)
#define F3(i,s,n) for(int i=s;i<=n;++i)
///////////////////////
const int maxn = 2e5+5;
ll t,n,r,b[maxn],c[maxn],pre[maxn];
ll temp,ans,ans_queue[maxn];
//不开ll一场空
bool ccc,fff;
/* 定义全局变量 */ 
void init()
{
    cin >> n ;
    F(n) cin>>r;
    ccc=1;fff=1;
    F(n) {
        cin>>c[i];
        if(c[i]<0) ccc=0;
        if(c[i]>0) fff=0;
        pre[i]=pre[i-1]+c[i];
        }
}
ll dfs(){
    ll ans=0;
    F(n) b[i]=i;
    do{
        temp=0;
        F(n){
            if(i==b[i]) continue;
            if(i>b[i]) temp+=c[i];
            else temp-=c[i];
        }```

    ans=max(ans,temp); }while(next_permutation(b+1,b+n+1));
return ans;

} ll cc(){ ll ans=0; F(n-1){ temp=pre[n]-pre[i]-c[i]; ans=max(temp,ans); } return ans; } ll _abs(ll c){return c>0 ? c: -c;} ll zj(){ ll ans=0; int x1=0,x2=0; for(int i=1;i<=n;i++) if(c[i]<0) {x1=i;break;} x1--; for(int i=n;i>=1;i--) if(c[i]>0) {x2=i;break;} x2++; /////// temp=0; if(x1>1) F3(i,1,x1-1){ temp=max(temp,pre[x1]-pre[i]-c[i]); } ans+=temp; /////// if(x1+1<=x2-1) F3(i,x1+1,x2-1) ans+=_abs(c[i]); /////// temp=0; if(x2<n) F3(i,x2+1,n){ temp=max(temp,-pre[i-1]+c[i]+pre[x2-1]); } ans+=temp return ans; } ll ff(){ ll ans=0; F3(i,2,n){ temp=-pre[i-1]+c[i]+pre[n-1]; ans=max(temp,ans); } return ans; } int main(){ cin>>t; while(t--){ init(); if(n<=8) ans=dfs(); else if(ccc) ans=cc(); else if(fff) ans=ff(); else ans=zj(); cout<<ans<<endl; } return 0; }