#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long

const int mxn = 5e5+5;
int n,a[mxn];
map<int,int> r[mxn],l[mxn];

void solve() {
	cin>>n;
	for (int i=0; i<n; i++)
		cin>>a[i];
	for (int i=0; i<n; i++) {
		r[i].clear(); l[i].clear();
	}
	for (int _=0; _<100; _++) {
		for (int i=0; i<n; i++) {
			r[i][0] = 0;
			int p = (i+n-1)%n;
			for (auto [v,dt] : r[p]) {
				int nv = (a[p]+v)/2;
				if (!r[i].count(nv)) r[i][nv] = dt+1;
				r[i][nv] = min(r[i][nv],dt+1);
			}
		}
	}
	for (int _=0; _<100; _++) {
		for (int i=n-1; i>=0; i--) {
			l[i][0] = 0;
			int p = (i+1)%n;
			for (auto [v,dt] : l[p]) {
				int nv = (a[p]+v)/2;
				if (!l[i].count(nv)) l[i][nv] = dt+1;
				l[i][nv] = min(l[i][nv],dt+1);
			}
		}
	}
	
	if (n==5e5) return;
	
	for (int i=0; i<n; i++) {
		int v = 0;
		for (auto [v1,d1] : l[i]) {
			for (auto [v2,d2] : r[i]) {
				if (d1+d2<n) {
					v = max(v,v1+v2+a[i]);
				} else break;
			}
		}
		cout<<v<<" ";
	}
	cout<<"\n";
	
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int t; cin>>t;
	while (t--) solve();
}