#include<bits/stdc++.h>
#define L(i,j,k) for(int i = (j); i <= (k); ++i)
#define R(i,j,k) for(int i = (j); i >= (k); --i)
#define ll long long
#define pb push_back
#define mk make_pair
#define sz(a) (int)(a).size()
using namespace std;
const int N = 1e4 + 4;
ll w[N];
int n;
ll f[N], g[N];
int lb(int wi){
    return wi & -wi;
}
void solve(){
    cin >> n;
    L(i, 1, n) cin >> w[i];
    sort(w + 1, w + n + 1);
    L(i, 1, n) w[i] += w[i - 1];
    g[0] = 0; 
    L(i, 1, n) g[i] = 1e18;
    L(i, 0, n){
        L(j, 0, n) f[j] = g[j], g[j] = 1e18;
        R(j, i, 0){
            if(j % 2 == 0 && j > 0){
                f[j / 2] = min(f[j / 2] ,f[j] + w[i]);
            }
            g[j + 1] = min(g[j + 1], f[j] + (lb(j) >> 1));
        }
        // L(j, 1, i)
        //     cout << f[j] << " ";
        // cout <<"\n";
    } 
    cout << f[1] <<"\n";
}
int main(){

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}