#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define int long long

void del(multiset <int> &ms , int val) {
  ms.erase(ms.find(val)) ;
}

void solve() {
  
    int n ;
    cin >> n ;
    vector <int> a(n) ;
    for(int i = 0 ; i < n ; i ++) cin >> a[i] ;
    sort(a.begin() , a.end()) ;
    reverse(a.begin() , a.end()) ;
    int ans = a[0] - a[1] ;
    int fans = ans ;
    for(int i = 2 ; i < n ; i ++) {
      if(a[i] <= 0) break ;
      if(i % 2 == 0) {
        ans += a[i] ;
        fans = min(fans , ans) ;
      } else {
        ans -= a[i] ;
      }
    }
    cout << fans << endl ;
  
}
       
     
      









int32_t main() {

    fastio();
    int t = 1;
    cin >> t;
    while (t--) solve();
}