#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
    inline int read(){
        int f(1),x(0);
        char ch=getchar();
        for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
        return f*x;
    }
    inline void Write(int x){
        if(x>9) Write(x/10);
        putchar(x%10+48);
    }
    inline void write(int x){
        if(x<0) putchar('-'),x=-x;
        Write(x);
        putchar('\n');
    }
}
using namespace Testify;
int n,T;
const int N=135;
int jinbi[N];
inline bool accepted(double delta,double t){
    if(delta<0){
        return true;
    }
    else if(exp(-delta/t)*RAND_MAX>rand()){
        return true;
    }
    return false;
}
int a[N],ansa,ansb,ans,mid;
mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
inline int random(int l,int r){
    return ((rd()%(r-l+1)+(r-l+1))%(r-l+1))+l;
}
inline void SA(){
    double t=3000;
    while(t>1e-15){
        int ra=random(1,mid);
        int rb=random(mid+1,n);
        int ea=ansa+a[rb]-a[ra];
        int eb=ansb+a[ra]-a[rb];
        int e=abs(ea-eb);
        if(accepted(double(e-ans),t)){
            ansa=ea,ansb=eb,ans=e;
            swap(a[ra],a[rb]);
        }
        t*=0.995;
    }
}
signed main(void){
    srand(time(0));
    T=read();
    while(T--){
        ansa=ansb=ans=0;
        n=read();
        for(register int i=1;i<=n;i++){
            jinbi[i]=read();
            a[i]=jinbi[i];
        }
        if(n==1){
            write(jinbi[1]);
            continue;
        }
        mid=(1+n)>>1;
        for(register int i=1;i<=mid;i++){
            ansa+=jinbi[i];
        }
        for(register int i=mid+1;i<=n;i++){
            ansb+=jinbi[i];
        }
        ans=abs(ansa-ansb);
        SA();
        SA();
        write(ans);
    }
    return 0;
}