#include <bits/stdc++.h>
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
#define per(i, t, f) for(int i(t); i >= f; --i)
#define pe(i, t) for(int i(t); i >= 1; --i)
#define nx(i, u) for(int i(head[u]); i; i = e[i].nxt)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
// #define int long long
using namespace std;
typedef pair <int, int> pii;
#define pb push_back
#define fi first
#define se second
#define ix(l, r) ((l + r) | (l != r))
#define ls (ix(l, mid))
#define rs (ix(mid + 1, r))
#define mp(i, j) (make_pair(i, j))
#define inf (int)(1e9+7)
#define INF 0x3f3f3f3f3f3f3f3f
#define eps 1e-10
#define look_memory cerr<<abs(&sT-&eD)/1024.0/1024<<'\n'
bool sT;


namespace IO {
char buf[1 << 21], *p1 = buf, *p2 = buf, buf1[1 << 21];
inline char gc() {
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}

#ifndef ONLINE_JUDGE
#endif

// #define gc getchar

template<class I>
inline void read(I &x) {
    x = 0;
    I f = 1;
    char c = gc();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = gc();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = gc();
    }
    x *= f;
}

template<class I>
inline void write(I x) {
    if (x == 0) {
        putchar('0');
        return;
    }
    I tmp = x > 0 ? x : -x;
    if (x < 0)
        putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        buf1[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(buf1[--cnt]);
}

#define in(x) read(x)
#define outn(x) write(x), putchar('\n')
#define out(x) write(x), putchar(' ')

} using namespace IO;

const int N = 1e4 + 5;
int T, n;
int a[N];
ll f[N*N/2];
ll pre[N];
int num[N];

#define lowbit(x) (x & (-x))

int id (int a, int b) {
	return num[a] + b + 1;
}

int main () {
	read(T);
	while(T--) {
		read(n);
		re(i, n) read(a[i]);
		sort(a + 1, a + n + 1);
		reverse(a + 1, a + n + 1);
		re(i, n) pre[i] = pre[i-1] + a[i];
		num[1] = n+1;
		rep(i, 2, n) {
			num[i] = num[i-1] + (n-i+2);
		}
		rep(i, 0, n) {
			rep(j, 0, n) f[id(i,j)] = INF;
		}
		f[id(0, 1)] = 0;
		rep(i, 0, n) {
			if(i) {
				rep(j, 0, n-i) {
					f[id(i, j)] = min(f[id(i, j)], f[id(i-1, j+1)] + (lowbit(j) >> 1));
				}
			}
			re(j, n-i) {
				if(j % 2 == 0) f[id(i, j)] = min(f[id(i, j)], f[id(i, j>>1)] + pre[n] - pre[i]);
			}
		}
		outn(f[id(n, 0)]);
	}
}