#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18;
const int N=1e4+5;
int T,n,w[N];
ll f[2][N],s[N];
void solve(){
	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)s[i]=s[i-1]+w[i];
	for(int i=0;i<=n;++i)f[0][i]=f[1][i]=inf;
	f[0][1]=0;
	for(int i=0,p=0,q=1;i<n;++i,p^=1,q^=1)
		for(int j=0;j<=n;++j)if(f[p][j]<inf){
			if(2*j<=n)f[p][2*j]=min(f[p][2*j],f[p][j]+s[n-i]);
			if(j)f[q][j-1]=min(f[q][j-1],f[p][j]+((j-1)&-(j-1)));
			f[p][j]=inf;
		}
	printf("%lld\n",f[n&1][0]-n+1);
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}