def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    a.sort()
    ans = 0
    for i in range(n // 2):
        ans += a[-i-1] - a[i]
    print(ans)
    
    
t = int(input())
for _ in range(t):
    solve()

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    
    sum = 0
    cnt = 0
    open = False
    for x in a:
        sum += abs(x)
        if x < 0 and not open:
            open = True
            cnt += 1
        if x > 0:
            open = False
 
    print(sum, cnt)

t = int(input())
for _ in range(t):
    n = int(input())
    s = 0
    while n >= 1:
        s += n
        n //= 2
    print(s)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<vector<int>> g;
vector<ll> cnt;
 
void dfs(int v, int p) {
    if (g[v].size() == 1 && g[v][0] == p) {
        cnt[v] = 1;
    } else {
        for (auto u : g[v]) {
            if (u != p) {
                dfs(u, v);
                cnt[v] += cnt[u];
            }
        }
    }
}
 
void solve() {
    int n, q;
    cin >> n;
 
    g.assign(n, vector<int>());
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    cnt.assign(n, 0);
    dfs(0, -1);
 
    cin >> q;
    for (int i = 0; i < q; i++) {
        int c, k;
        cin >> c >> k;
        c--; k--;
 
        ll res = cnt[c] * cnt[k];
        cout << res << '\n';
    }
}
 
signed main() {
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
    }
 
    return 0;
}

def solve():
    n, m = map(int, input().split())
    segs = []
    for i in range(m):
        l, r = map(int, input().split())
        l -= 1
        segs.append([l, r])
    q = int(input())
    ord = [0] * q
    for i in range(q):
        ord[i] = int(input())
        ord[i] -= 1
    l = 0
    r = q + 1
    while r - l > 1:
        M = (l + r) // 2
        cur = [0] * n
        for i in range(M):
            cur[ord[i]] = 1
        pr = [0] * (n + 1)
        for i in range(n):
            pr[i+1] = pr[i] + cur[i]
        ok = False
        for i in segs:
            if(pr[i[1]] - pr[i[0]] > (i[1] - i[0]) // 2):
                ok = True
                break
        if ok:
            r = M
        else:
            l = M
    if r == q + 1:
        r = -1
    print(r)
 
tc = int(input())
for T in range(tc):
    solve()

class info:
    mn_suf = 0
    mx_suf = 0
    mn_ans = 0
    mx_ans = 0
 
def solve():
    n = int(input())
    
    start = info()
    start.mx_suf = start.mx_ans = 1
    
    st = [start]
    for i in range(n):
        com = input().split()
        if (com[0] == '+'):
            v = int(com[1]) - 1
            x = int(com[2])
 
            pref = st[v]
            cur = info()
 
            cur.mn_suf = min(0, pref.mn_suf + x)
            cur.mx_suf = max(0, pref.mx_suf + x)
            cur.mn_ans = min(pref.mn_ans, cur.mn_suf)
            cur.mx_ans = max(pref.mx_ans, cur.mx_suf)
 
            st.append(cur)
        else:
            v = int(com[2]) - 1
            x = int(com[3])
 
            if st[v].mn_ans <= x <= st[v].mx_ans:
                print("Yes")
            else:
                print("No")
 
t = int(input())
for testCase in range(t):
    solve()

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
struct info {
    int sum, minPrefL, maxPrefL, minPrefR, maxPrefR, minSeg, maxSeg;
 
    info(int el = 0) {
        sum = el;
        minSeg = minPrefL = minPrefR = min(el, 0);
        maxSeg = maxPrefL = maxPrefR = max(el, 0);
    }
};
 
struct question {
    int u, v, x;
};
 
info merge(info& a, info& b) {
    info res;
    res.sum = a.sum + b.sum;
    res.minPrefL = min(a.minPrefL, a.sum + b.minPrefL);
    res.maxPrefL = max(a.maxPrefL, a.sum + b.maxPrefL);
    res.minPrefR = min(a.minPrefR + b.sum, b.minPrefR);
    res.maxPrefR = max(a.maxPrefR + b.sum, b.maxPrefR);
    res.minSeg = min({a.minSeg, b.minSeg, a.minPrefR + b.minPrefL});
    res.maxSeg = max({a.maxSeg, b.maxSeg, a.maxPrefR + b.maxPrefL});
    return res;
}
 
const int MAXN = 200100;
const int lg = 17;
 
int up[lg + 1][MAXN];
info ans[lg + 1][MAXN];
int d[MAXN];
 
void solve() {
    int n;
    cin >> n;
 
    for (int i = 0; i <= lg; i++) up[i][0] = 0;
    ans[0][0] = info(1);
    d[0] = 0;
 
    int cur = 0;
    for (int q = 0; q < n; q++) {
        char c;
        cin >> c;
        if (c == '+') {
            int v, x;
            cin >> v >> x;
            v--;
            cur++;
 
            d[cur] = d[v] + 1;
 
            up[0][cur] = v;
            for (int j = 0; j <= lg - 1; j++) up[j + 1][cur] = up[j][up[j][cur]];
 
            ans[0][cur] = info(x);
            for (int j = 0; j <= lg - 1; j++) ans[j + 1][cur] = merge(ans[j][cur], ans[j][up[j][cur]]);
        } else {
            int u, v, x;
            cin >> u >> v >> x;
            u--; v--;
            
            if (d[u] < d[v]) swap(u, v);
 
            int dif = d[u] - d[v];
            info a, b;
            for (int i = lg; i >= 0; i--) {
                if ((dif >> i) & 1) {
                    a = merge(a, ans[i][u]);
                    u = up[i][u];
                }
            }
 
            if (u == v) {
                a = merge(a, ans[0][u]);
            } else {
                for (int i = lg; i >= 0; i--) {
                    if (up[i][u] != up[i][v]) {
                        a = merge(a, ans[i][u]);
                        u = up[i][u];
                        b = merge(b, ans[i][v]);
                        v = up[i][v];
                    }
                }
 
                a = merge(a, ans[1][u]);
                b = merge(b, ans[0][v]);
            }
 
            swap(b.minPrefL, b.minPrefR);
            swap(b.maxPrefL, b.maxPrefR);
 
            info res = merge(a, b);
            if (res.minSeg <= x && x <= res.maxSeg) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }
}
 
int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
    }
}