#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,B=30,M=N/B+5;
bool stt;
int T,n,a[N];
namespace work1
{
	const int N=2e3+5;
	int r[N][N],l[N][N];
	ll ans[N];
	void solve()
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<n;j++)
			{
				int giv=0;
				for(int k=i+j;k>i;k--)giv=(giv+a[k])/2;
				r[i][j]=giv;
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<n;j++)
			{
				int giv=0;
				for(int k=i+n-j;k<i+n;k++)giv=(giv+a[k])/2;
				l[i][j]=giv;
			}
		}
		for(int i=1;i<=n;i++)ans[i]=0;
		for(int i=1;i<=n;i++)for(int j=0;j<n;j++)ans[i]=max(ans[i],(ll)a[i]+l[i][j]+r[i][n-1-j]);
		for(int i=1;i<=n;i++)printf("%lld ",ans[i]);printf("\n");
	}
}
namespace work2
{
	int bel[N],L[N],R[N],aa[M],b[M],ar[N],p[M][16][2],br[N],al[N],bl[N];
	int ask(int nl,int nr)
	{
		if(bel[nl]+1>=bel[nr])
		//if(1)
		{
			//cout<<"?"<<nl<<" "<<nr<<endl;
			int giv=0;
			for(int i=nr;i>=nl;i--)giv=(giv+a[i])>>1;
			return giv;
		}
		else
		{
			int giv=0;
			for(int i=nr;bel[i]==bel[nr];i--)giv=(giv+a[i])>>1;
			int nl1=bel[nl]+1,nr1=bel[nr]-1,tp=(giv>=b[nr1]);
			if(nl1<=nr1)
			{
				//cout<<tp<<" "<<nl1<<" "<<nr1<<endl;
				//cout<<p[4][1][1]<<endl;
				for(int i=15;i>=0;i--)if(nr1-(1<<i)>=nl1)tp=p[nr1][i][tp],nr1-=(1<<i);
				giv=aa[nl1]+tp;
				//cout<<tp<<endl;
			}
			for(int i=R[bel[nl]];i>=nl;i--)giv=(giv+a[i])>>1;
			return giv;
		}
	}
	ll ans[N];
	void solve()
	{
		for(int i=1;i<=n*2;i++)bel[i]=(i-1)/B+1;
		for(int i=1;i<=bel[n*2];i++)L[i]=(i-1)*B+1,R[i]=min(i*B,n*2);
		for(int i=1;i<=bel[n*2];i++)
		{
			int giv=0;
			for(int j=R[i];j>=L[i];j--)giv=(giv+a[j])>>1;
			aa[i]=giv;
			int nl=1,nr=1e9,res=1e9+1;
			while(nl<=nr)
			{
				int mid=nl+nr>>1,giv1=mid;
				for(int j=R[i];j>=L[i];j--)giv1=(giv1+a[j])>>1;
				if(giv1>giv)res=mid,nr=mid-1;
				else nl=mid+1;
			}
			b[i]=res;
		}
		for(int i=1;i<=bel[n*2];i++)
		{
			if(aa[i]>=b[i-1])p[i][0][0]=1;else p[i][0][0]=0;
			if(aa[i]+1>=b[i-1])p[i][0][1]=1;else p[i][0][1]=0;
			for(int j=1;j<=15;j++)if(i-(1<<j-1)>=0)for(int k=0;k<2;k++)p[i][j][k]=p[i-(1<<j-1)][j-1][p[i][j-1][k]];
		}
		//cout<<p[4][1][1]<<endl;
		//cout<<p[4][0][1]<<" "<<p[]endl;
		//cout<<ask(4,17)<<endl;
		//cout<<bel[4]<<" "<<bel[17]<<endl;
		//for(int i=2;i<=4;i++)cout<<aa[i]<<" "<<b[i]<<endl;
		for(int i=1;i<=n;i++)
		{
			ar[i]=ask(i+1,i+B);
			int nl=i+B+1,nr=i+n-1,res=i+n;
			while(nl<=nr)
			{
				int mid=nl+nr>>1;
				if(ask(i+1,mid)>ar[i])res=mid,nr=mid-1;
				else nl=mid+1;
			}
			br[i]=res;
		}

		reverse(a+1,a+n+1);for(int i=1;i<=n;i++)a[i+n]=a[i];
		for(int i=1;i<=bel[n*2];i++)
		{
			//cout<<i<<" "<<R[i]<<" "<<L[i]<<endl;
			int giv=0;
			for(int j=R[i];j>=L[i];j--)giv=(giv+a[j])>>1;
			aa[i]=giv;
			int nl=1,nr=1e9,res=1e9+1;
			while(nl<=nr)
			{
				int mid=nl+nr>>1,giv1=mid;
				for(int j=R[i];j>=L[i];j--)giv1=(giv1+a[j])>>1;
				if(giv1>giv)res=mid,nr=mid-1;
				else nl=mid+1;
			}
			b[i]=res;
		}
		//cout<<aa[6]<<" "<<b[6]<<endl;
		for(int i=1;i<=bel[n*2];i++)
		{
			if(aa[i]>=b[i-1])p[i][0][0]=1;else p[i][0][0]=0;
			if(aa[i]+1>=b[i-1])p[i][0][1]=1;else p[i][0][1]=0;
			for(int j=1;j<=15;j++)if(i-(1<<j-1)>=0)for(int k=0;k<2;k++)p[i][j][k]=p[i-(1<<j-1)][j-1][p[i][j-1][k]];
		}
		//cout<<ask(20,25)<<endl;
		//cout<<bel[20]<<" "<<bel[25]<<endl;
		for(int i=1;i<=n;i++)
		{
			al[n-i+1]=ask(i+1,i+B);
			int nl=i+B+1,nr=i+n-1,res=i+n;
			while(nl<=nr)
			{
				int mid=nl+nr>>1;
				if(ask(i+1,mid)>al[n-i+1])res=mid,nr=mid-1;
				else nl=mid+1;
			}
			bl[n-i+1]=n-i+1+n-(res-i);
		}
		reverse(a+1,a+n+1);for(int i=1;i<=n;i++)a[i+n]=a[i];

		for(int i=1;i<=n;i++)
		{
			//cout<<al[i]<<" "<<ar[i]<<" "<<bl[i]<<" "<<br[i]<<" "<<a[i]<<endl;
			ans[i]=al[i]+ar[i];
			if(br[i]<bl[i])ans[i]=max(ans[i],(ll)al[i]+ar[i]+2);
			if(br[i]<i+n-B)ans[i]=max(ans[i],(ll)al[i]+ar[i]+1);
			else if(br[i]<i+n)
			{
				int giv=0;
				for(int j=br[i]+1;j<i+n;j++)giv=(giv+a[j])>>1;
				ans[i]=max(ans[i],(ll)ar[i]+1+giv);
			}
			if(bl[i]>i+B)ans[i]=max(ans[i],(ll)al[i]+ar[i]+1);
			else if(bl[i]>i)
			{
				int giv=0;
				for(int j=br[i]+1;j<i+n;j++)giv=(giv+a[j])>>1;
				ans[i]=max(ans[i],(ll)al[i]+1+giv);
			}
			ans[i]+=a[i];
		}
		for(int i=1;i<=n;i++)printf("%lld ",ans[i]);printf("\n");
	}
}
void solve()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];
	if(n<=300){work1::solve();return ;}
	work2::solve();
}
bool edd;
int main()
{
	cerr<<((&stt)-(&edd))/1024.0/1024<<"\n";
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}