#include<bits/stdc++.h>
#define ll long long
#define N 10005
using namespace std;
const ll INF=1e18;
int n,w[N];
ll val[N],sum[N],dp[N][N];
inline void tomin(ll &a,ll b){a=min(a,b);return;}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&w[i]);
		sort(w+1,w+n+1);
		for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[i];
		for(int i=1;i<=n;i++) val[i]=(i&-i)-__builtin_popcount(i&-i)-1;
		for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) dp[i][j]=INF;
		dp[0][0]=1;
		for(int i=0;i<=n;i++){
			for(int j=i;j>=0;j--){
				if(i+1<=n) tomin(dp[i+1][j+1],dp[i][j]+val[j+1]);
				if(~j&1) tomin(dp[i][j/2],dp[i][j]+sum[i]);
			}
		}
		printf("%lld\n",dp[n][1]);
	}
}