#include<bits/stdc++.h>
using namespace std;
typedef long ll;
const int MAXN = 1e5+10;
void tomin(int& x,int y){x = min(x,y);}
void tomax(int& x,int y){x = max(x,y);}
//
int T,n; string s;

namespace SA{
    int rk[MAXN*2],oldrk[MAXN*2],cnt[MAXN],sa[MAXN],tmp[MAXN],m;
    void build(){
        fill(rk+1,rk+1+2*n,0); fill(oldrk+1,oldrk+1+2*n,0);
        m = max(n,150); fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;i++)rk[i] = s[i],cnt[rk[i]]++;
        for(int i=1;i<=m;i++)cnt[i] += cnt[i-1];
        for(int i=n;i>=1;i--)sa[cnt[rk[i]]--] = i;
        for(int w=1,tot;w<n;w<<=1){
            tot = 0; for(int i=n-w+1;i<=n;i++)tmp[++tot] = i;
            for(int i=1;i<=n;i++)if(sa[i]>w)tmp[++tot] = sa[i]-w;
            fill(cnt+1,cnt+1+m,0);
            for(int i=1;i<=n;i++)cnt[rk[i]]++;
            for(int i=1;i<=m;i++)cnt[i] += cnt[i-1];
            for(int i=n;i>=1;i--)sa[cnt[rk[tmp[i]]]--] = tmp[i];
            //
            for(int i=1;i<=n;i++)oldrk[i] = rk[i];
            rk[sa[1]] = 1;
            for(int i=2;i<=n;i++){
                rk[sa[i]] = rk[sa[i-1]] + \
                !(oldrk[sa[i]] == oldrk[sa[i-1]] && oldrk[sa[i]+w] == oldrk[sa[i-1]+w]);
            }
        }
    }
} using SA::rk;

#define lowbit(x) (x&(-x))
struct BIT{
    int t[MAXN];
    void init(){fill(t+1,t+1+n,n+1);}
    void mdf(int x,int v){for(;x<=n;x+=lowbit(x))tomin(t[x],v);}
    int qry(int x){int S=n+1;for(;x;x-=lowbit(x))tomin(S,t[x]);return S;}
}bit;

int ans[MAXN];

void solve(){
    cin>>n>>s; s=" "+s;
    if(n==1)return void(cout<<"1\n");
    SA::build(); bit.init();
    for(int i=n;i>=1;i--){
        int pos = bit.qry(rk[i]); ans[i] = pos-i;
        bit.mdf(rk[i],i);
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" "; cout<<"\n";
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>T;
    while(T--)solve();

    return 0;
}