rt.

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 100;

int t, n, a[N], ans = 1e9;

int check() {
  int sum1 = 0, sum2 = 0;
  for (int i = 1; i <= (n + 1) / 2; i++) {
    sum1 += a[i];
  }
  for (int i = (n + 1) / 2 + 1; i <= n; i++) {
    sum2 += a[i];
  }
  return abs(sum1 - sum2);
}

void Sa() {
  double T = 3000;
  while (T > 1e-10) {
    int x = rand() % n + 1;
    int y = rand() % n + 1;
    swap(a[x], a[y]);
    int sum = check();
    if (sum  < ans) {
      ans = sum;
    } else if ((exp(-(sum - ans) / T) * RAND_MAX > rand())) {
      swap(a[x], a[y]);
    }
    T *= 0.997;
  }
}

void solve() {
  for (int i = 1; i <= 100; i++) {
    Sa();
  }
}

int main() {
  srand(time(NULL));
  cin >> t;
  while (t--) {
    cin >> n;
    ans = 1e9;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    if (n == 1) {
      cout << a[1] << endl;
      continue;
    }
    solve();
    cout << ans << endl;
  } 
  return 0;
}