#include<bits/stdc++.h>

using i64 = long long int;
using u64 = unsigned long;
using d96 = long double;

void solve(){
    int n;
    std::cin>>n;
    std::vector<int>v(n);
    for(int i = 0;i<n;i++){
        std::cin>>v[i];
    }
    std::sort(v.rbegin(), v.rend());
    i64 ans = 0;
    i64 best = 0;
    int f1 = 0, f2 = 0;
    for(int i = 0;i<n;i++){
        if(i % 2 == 0){
            best = std::max(best, ans);
            if(ans + v[i] > ans){
                ans = ans + v[i];
            }else{
                if(f1 > 0) break;
            }
            f1++;
        }
        else {
            if(ans - v[i] < ans){
                ans = ans - v[i];
            }
            else if(f2 > 0) break;
            f2++;
        }
    }
    best = std::max(best, ans);
    std::cout<<best<<'\n';
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    std::cin>>t;
    while(t--){
        solve();
    }

    return 0;
}