#include <bits/stdc++.h>
#define int long long
#define db double

using namespace std;

const int maxn = 1e5 + 10;
const db tem_S = 5000;
const db tem_R = 0.9112;
const db tem_E = 1e-10;
const db e = 2.718281828;
const int inf = 1e9;
const int tem_C = 1e3;

int T, n, m, ans;
int a[maxn];
mt19937 eng;

double rd(double l, double r) {
	uniform_real_distribution<double> dist(l, r);
	return dist(eng);
}

int rdi(int l, int r) {
	uniform_int_distribution<int> dist(l, r);
	return dist(eng);
}

void solve() {
	db t = tem_S;
	while (t > tem_E) {
		int x = rdi(1, n), y = rdi(1, n);
		int s1 = 0, s2 = 0;
		swap(a[x], a[y]);
		for (int i = 1; i <= m; i++) s1 += a[i];
		for (int i = m + 1; i <= n; i++) s2 += a[i];
		swap(a[x], a[y]);
		int d = abs(s1 - s2);
		if (d < ans) {
			ans = d;
			swap(a[x], a[y]);
		} else {
			db p = pow(e, (ans - d) / t);
			db q = rd(0.0, 1.0);
			if (q <= p) {
				ans = d;
				swap(a[x], a[y]);
			}
		}
		t *= tem_R;
	}
}

signed main() {
	srand(time(0));
	eng = mt19937(rand());
	cin >> T;
	while (T--) {
		cin >> n, m = (n + 1) / 2, ans = inf;
		for (int i = 1; i <= n; i++) cin >> a[i];
		int cnt = tem_C;
		while (cnt--) solve();
		cout << ans << endl;
	}
	return 0;
}