#include<bits/stdc++.h>
#define N 100005
using namespace std;
int T,n;
char s[N];
int sz;
int rak[N],sa[N],tp[N],c[N];
void Rsort(){
    for(int i=0;i<=sz;++i) c[i]=0;
    for(int i=1;i<=n;++i) ++c[rak[i]];
    for(int i=1;i<=sz;++i) c[i]+=c[i-1];
    for(int i=n;i>=1;--i) sa[c[rak[tp[i]]]--]=tp[i];
}
void sa_build(){
    sz=127;
    for(int i=1;i<=n;++i)
        rak[i]=s[i],tp[i]=i;
    Rsort();
    for(int w=1,p=0;p<n;sz=p,w<<=1){
        assert(w<=n);
        p=0;
        for(int i=1;i<=w;++i)
            tp[++p]=n-w+i;
        for(int i=1;i<=n;++i)
            if(sa[i]>w)
                tp[++p]=sa[i]-w;
        Rsort();
        swap(tp,rak);
        rak[sa[1]]=p=1;
        for(int i=2;i<=n;++i)
            rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
    }
}
int tr[N],ans[N];
void init(){
    for(int i=1;i<=n;++i) tr[i]=n+1;
}
void modify(int x,int v){
    for(int i=x;i<=n;i+=i&(-i)) tr[i]=min(tr[i],v);
}
int qry(int x){
    int res=n+1;
    for(int i=x;i;i-=i&(-i)) res=min(res,tr[i]);
    return res;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%s",&n,s+1);
        sa_build();
        init();
        for(int i=n;i>=1;--i){
            assert(rak[i]>0);
            ans[i]=qry(rak[i])-1;
            modify(rak[i],i);
        }
        for(int i=1;i<=n;++i)
            printf("%d ",ans[i]-i+1);
        puts("");
        for(int i=1;i<=n;++i) sa[i]=rak[i]=tp[i]=0;
    }
    return 0;
}