#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define lowbit(x) (x&(-x))
const int mod=998244353;
const double eps=1e-12;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
int dcmp(double x){if(fabs(x)<eps)return 0;return x>0?1:-1;}

// #define int ll

const int N=400050;
string S;
int nxt[N];
//sa[i]表示排名为i的后缀suffix(id),rk[i]表示后缀suffix(i)的排名
//ht[i]表示排名为i和i-1的后缀的lcp长度
int s[N];
int sa[N],rk[N],oldrk[N<<1],id[N],px[N],cnt[N],ht[N];
bool cmp(int x,int y,int w){
    return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
}
void get_sa(int *s,int len){
    memset(cnt,0,sizeof cnt);
    //如果是多组数据需要特别注意这边的复杂度
    int i,n,m=max(len+1,500),p,w;
    //桶的上界可能达到len+1,注意修改m的值
    n=len;
    for(i=1;i<=n;i++)++cnt[rk[i]=s[i]];
    for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
    for(i=n;i>=1;--i)sa[cnt[rk[i]]--]=i;
    for(w=1;;w<<=1,m=p){
        for(p=0,i=n;i>n-w;i--)id[++p]=i;
        for(i=1;i<=n;i++)if(sa[i]>w)id[++p]=sa[i]-w;
        memset(cnt,0,sizeof cnt);
        //如果是多组数据需要特别注意这边的复杂度
        for(i=1;i<=n;i++)++cnt[px[i]=rk[id[i]]];
        for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
        for(i=n;i>=1;i--)sa[cnt[px[i]]--]=id[i];
        memcpy(oldrk,rk,sizeof rk);
        //如果是多组数据需要特别注意这边的复杂度
        for(p=0,i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
        if(p==n){
            for(int i=1;i<=n;i++)sa[rk[i]]=i;
            break;
        }
    }
    int j;
    for(i=1,j=0;i<=len;i++){
        if(j)--j;
        while(s[i+j]==s[sa[rk[i]-1]+j])++j;
        ht[rk[i]]=j;
    }
}
int len(int x){int ans=0;while(x)ans++,x>>=1;return ans;}
int mi[25][N];
void build(int n)
{
    for(int i=1;i<=n;i++)mi[0][i]=ht[i];
    for(int j=1;j<25;j++)
    {
        for(int i=1;i<=n-(1<<j)+1;i++)
        {
            mi[j][i]=min(mi[j-1][i],mi[j-1][i+(1<<(j-1))]);
        }
    }
}
int query(int l,int r)
{
    int k=len(r-l+1)-1;
    return min(mi[k][l],mi[k][r-(1<<k)+1]);
}
int Query(int L,int R)
{
    int l=min(rk[L],rk[R]);
    int r=max(rk[L],rk[R]);
    return query(l+1,r);
}
int cmp(int l1,int r1,int l2,int r2)
{
    int len=Query(l1,l2);
    if(r1-l1+1<=len&&r2-l2+1<=len)return 0;// ==
    else if(r1-l1+1<=len)return -1;// <
    else if(r2-l2+1<=len)return 1;// >
    else
    {
        if(S[l1+len-1]>S[l2+len-1])return 1;// >
        else return -1;// <
    }
}

void solve()
{
    int n;
    cin>>n;
    cin>>S;
    // for(int i=1;i<=n;i++)S.push_back('a'+rand()%26);
    for(int i=1;i<=n;i++)s[i]=S[i-1];
    get_sa(s,n);
    build(n);
    for(int i=1;i<=n;i++)nxt[i]=1;
    for(int i=n;i>=1;i--)
    {
        int j=i+1;
        while(j<=n)
        {
            // cout<<i<<' '<<j-1<<' '<<j<<' '<<j+nxt[j]-1<<' '<<cmp(i,j-1,j,j+nxt[j]-1)<<'\n';
            if(cmp(i,j-1,j,j+nxt[j]-1)<0)
            {
                j=j+nxt[j];
            }
            else
            {
                break;
            }
        }
        nxt[i]=j-i;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<nxt[i]<<" \n"[i==n];
    }
}

/*

*/

#undef int

int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    // cout<<fixed<<setprecision(15);



    int _;cin>>_;while(_--)
    {
        solve();
    }
    return 0;
}