/*
考虑建模，将合并操作当作新建一个节点，作为合并的两摞书的父节点，相当于合并后的一摞书 
考虑这样建出的二叉树可以唯一的确定一种合并方案，考虑这种合并方案的贡献怎么计算 
考虑每个叶子结点代表最开始的一本书，重量值的贡献就是每本书的 W 乘上该节点的深度 
考虑磨损值怎么计算，考虑进行长链剖分，因为对于一个节点，其磨损值一定是取决于其子树中最深的深度，因为合并时我们肯定选小磨损值贡献 
考虑进行长链剖分后，考虑每条链只会做 2^(n-1)-1 的贡献 
我们考虑设计状态 f(i,j) 表示已经钦定了 i 个节点为叶子，当前层还有 j 个节点不是叶子，n<i+j 的状态是不合法的，可以减掉 
考虑转移，可以结束当前层的决策，f(i,2*j)=f(i,j)+sigma(w(k))(k>i) 
可以钦定一个叶子，f(i+1,j-1)=f(i,j)+lowbit(j)/2 
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mn=10086;
int T,n,w[mn];
int n2[30],lb[mn];
ll sumw[mn],dp[2][mn];
int now,to;
ll ans;

int read(){
	int x=0,w=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') w=-1;
		ch=getchar();
	} 
	while(ch>='0' && ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*w;
} 

void ready(){
	n2[0]=1;
	for(int i=1;i<=20;i++) n2[i]=n2[i-1]<<1;
	for(int i=0;i<=13;i++){
		for(int j=n2[i];j<=1e4;j+=n2[i+1]) lb[j]=n2[i];
	}
	return;
}

void clear(){
	for(int i=0;i<=n;i++) dp[now][i]=1e18;
	return;
}

int main(){
	T=read();
	
	ready();
	
	while(T--){
		n=read();
		for(int i=1;i<=n;i++) w[i]=read();
		
		sort(w+1,w+n+1);
		sumw[0]=0;
		for(int i=1;i<=n;i++) sumw[i]=sumw[i-1]+w[i];
		
		for(int i=0;i<=1;i++) for(int j=0;i+j<=n;j++) dp[i][j]=1e18;
		dp[0][1]=0;
		now=1,to=0;
		for(int i=0;i<n;i++){
			now=(now+1)%2,to=(now+1)%2;
			for(int j=1;i+j<=n;j++){
				if((j<<1)<=n) dp[now][j<<1]=min(dp[now][j<<1],dp[now][j]+sumw[n-i]);
				dp[to][j-1]=min(dp[to][j-1],dp[now][j]+lb[j-1]);
			}
			clear();
		}
		
		ans=dp[to][0]-(n-1);
		
		cout<<ans<<endl;
	}
	
	return 0;
}
/*
5
6
1 1 4 5 1 4
6
10 10 40 50 10 40
5
1000000000 1000000000 1000000000 1000000000 1000000000
6
1 3 15 105 945 27455185
6
1 2 3 4 5 6

1
4
1 1 1 1
*/