#include<bits/stdc++.h>

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define eb emplace_back
#define IL inline
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Fol(i,k,j) for(int i=(k);i>=(j);i--)

using namespace std;

#define N 500005

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

void debug(auto &&...x){
    ((cerr<<x<<' '),...);
    cerr<<'\n';
}

deque<pi> f,g;
vector<pi> L[N],R[N];
int a[N],n;

void init(int opt){
    f.push_back(mp(n,a[n]));
    Fol(i,n-1,1){
        g.push_back(mp(i,a[i]));
        for(auto [id,val]:f){
            if(val/2+a[i]!=g.back().se)g.push_back(mp(id,val/2+a[i]));
        }
        swap(f,g);
        while(g.size())g.pop_back();
    }
    if(opt)for(auto _:f)L[1].pb(_);
    else for(auto _:f)R[n].eb(n-_.fi+1,_.se);
    Fol(i,n,2){
        if(f.back().fi==i)f.pop_back();
        g.push_back(mp(i,a[i]));
        for(auto [id,val]:f){
            if(val/2+a[i]!=g.back().se)g.push_back(mp(id,val/2+a[i]));
        }
        swap(f,g);
        for(auto _:f){
            if(opt)L[i].pb(_);
            else R[n-i+1].eb(n-_.fi+1,_.se);
        }
        while(g.size())g.pop_back();
    }
}

void solve(){
    n=read();
    For(i,1,n)a[i]=read(),L[i].clear(),R[i].clear();init(1);
    reverse(a+1,a+n+1);init(0);reverse(a+1,a+n+1);
    auto dis1=[&](int x,int y){
        if(x<=y)return y-x;
        else return y+n-x;
    };
    auto dis2=[&](int x,int y){
        if(y<=x)return x-y;
        else return x+n-y;
    };
    For(i,1,n){
        int pos=R[i].size()-1,res=0;
        for(auto [id,val]:L[i]){
            
            while(pos>=0 && dis1(i,id)+dis2(i,R[i][pos].fi)>=n)pos--;
            if(pos>=0)res=max(res,val+R[i][pos].se-a[i]);
            res=max(res,val);
        }
        for(auto [id,val]:R[i]){
            //debug(i,id,val,dis1(i,id));
            res=max(res,val);
        }
        write(res);putchar(' ');
    }
    putchar('\n');
}

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #endif

    int T=read();while(T--)solve();
    return 0;
}