#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<int,int> PII;
int n,m,k;
int a[N];
bool tf[N];
int id[N];
int ji[N],ou[N];
int rev[N];

void __(){
	scanf("%d",&n);
	for(int i=1;i<N;i++){
		tf[i]=0;
		id[i]=0;
	}
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		tf[a[i]]=1;
	}
	vector<int> v;
	for(int i=1;i<N;i++){
		if(tf[i]){
			v.push_back(i);
			
		}
	}
	for(int i=0;i<v.size();i++) id[v[i]]=i+1;
	int mx=v.back();
	for(int i=1;i<=mx;i++){
		for(auto j:v){
			int x=j/i,y=j%i;
			if(x&1){
				ji[j]=(x+1)/2*i;
				ou[j]=x/2*i;
				if(y==0){
					rev[j]=1;
				}else{
					ou[j]+=y;
					rev[j]=0;
				}
			}else{
				ji[j]=x/2*i;
				ou[j]=x/2*i;
				if(y==0){
					
					rev[j]=0;
				}else{
					ji[j]+=y;
					rev[j]=1;
				}
			}
		}
		int now=1;
		int ans=0;
		for(int j=1;j<=n;j++){
			if(now) ans+=ji[a[j]];
			else ans+=ou[a[j]];
			now^=rev[a[j]];
		}
		printf("%d\n",ans);
	}
	
}
/*
1
4
10 7 2 8
*/
int main(){
	int _;
	cin>>_;
	while(_--){
		__();
	}
}