#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const ll Mod=(1ll<<61)-1;
const int base=233;
const int N=1e5+50;
char str[N];
__int128 h[N];
__int128 sum[N];
ll ha(int l,int r) {
    __int128 v=(sum[r]-sum[l-1]*h[r-l+1])%Mod;
    if(v<0) v+=Mod;
    return v;
}
bool cmp(int a,int b,int c,int d) {
    int L=1,R=min(b-a+1,d-c+1),l=0;
    while(L<=R) {
        int mid=L+R>>1;
        if(ha(a,a+mid-1)==ha(c,c+mid-1)) l=mid,L=mid+1;
        else R=mid-1;
    }
    int pa=a+l,pc=c+l;
    // cerr << a << ' ' << b << ' ' << c << ' ' << d << ' ' << l << endl;
    if(pa>b && pc>d) return 0;
    else if(pa>b) return 1;
    else if(pc>d) return 0;
    else return str[pa]<str[pc];
}
int stk[N];
int ans[N];
void solve() {
    int n;
    cin >> n;
    cin >> str+1;
    h[0]=1;
    FOR(i,1,n) h[i]=h[i-1]*base%Mod;
    FOR(i,1,n) sum[i]=(sum[i-1]*base+str[i])%Mod;
    int K=0;
    stk[K]=n+1;
    // cerr << " -- " << endl;
    DOR(i,n,1) {
        // cerr << i << endl;
        while(K && cmp(i,stk[K]-1,stk[K],stk[K-1]-1)) {
            --K;
        }
        // cerr << i << endl;
        ans[i]=stk[K]-i;
        stk[++K]=i;
    }
    FOR(i,1,n) cout << ans[i] << " \n"[i==n];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}