#include<bits/stdc++.h>
#define N 500005
using namespace std;
int n,a[N*2];
int pos[N][51],val[N][51],c[N];
int P[51],V[51],cnt,pp[51],vv[51];
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) a[i+n]=a[i];
	cnt=0;
	for(int i=2*n;i>=1;i--){
		int cc=cnt;
		for(int j=1;j<=cc;j++) pp[j]=P[j],vv[j]=V[j]/2+a[i];
		cnt=1;P[1]=i,V[1]=a[i];
		for(int j=1;j<=cc;j++){
			cnt+=(vv[j]!=V[cnt]);
			V[cnt]=vv[j];P[cnt]=pp[j];
		}
		if(i<=n){
			c[i]=cnt;
			for(int j=1;j<=cnt;j++)
				pos[i][j]=P[j],val[i][j]=V[j];
		}
	}
	cnt=0;
	for(int i=1;i<=2*n;i++){
		int cc=cnt;
		for(int j=1;j<=cc;j++) pp[j]=P[j],vv[j]=V[j]/2+a[i];
		cnt=1;P[1]=i,V[1]=a[i];
		for(int j=1;j<=cc;j++){
			cnt+=(vv[j]!=V[cnt]);
			V[cnt]=vv[j];P[cnt]=pp[j];
		}
		if(i==n*2){
			long long ans=2*a[i];P[0]=i+1;pos[i-n][0]=i-n-1;
			for(int j=1,k=cnt;j<=c[i-n];j++){
				while(k>0&&P[k-1]-1<=pos[i-n][j-1]+1) k--;
				if(k>0) ans=max(ans,0ll+V[k]+val[i-n][j]);
			}
			printf("%lld ",ans-a[i]);
		}
	}
	printf("\n");
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--) solve();
}