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

typedef long long ll;
const int N = 5e5 + 10;

struct SA {
	int n, m = 122; string s;//m为最大字符的Ascll码 
	int x[N], y[N], c[N], sa[N], rk[N], height[N];
	inline void get_sa() {
		m = 122;
		for(int i = 0; i <= m; ++i) c[i] = 0;
		for(int i = 1; i <= n; ++i) ++c[x[i] = s[i]];
		for(int i = 2; i <= m; ++i) c[i] += c[i - 1];
		for(int i = n; i >= 1; --i) sa[c[x[i]] -- ] = i;
		for(int k = 1; k <= n; k <<= 1) {
			int num = 0;
			for(int i = n - k + 1; i <= n; ++i) y[++num] = i;
			for(int i = 1; i <= n; ++i) if(sa[i] > k) y[++num] = sa[i] - k;
			for(int i = 1; i <= m; ++i) c[i] = 0;
			for(int i = 1; i <= n; ++i) c[x[i]] ++ ;
			for(int i = 2; i <= m; ++i) c[i] += c[i - 1];
			for(int i = n; i >= 1; --i) {sa[c[x[y[i]]] -- ] = y[i]; y[i] = 0;}
			swap(x, y);
			num = 1; x[sa[1]] = 1;
			for(int i = 2; i <= n; ++i) {
				if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num;
				else x[sa[i]] = ++num;
			}
			if(num == n) break;
			m = num;
		}
		for(int i = 1; i <= n; ++i) rk[sa[i]] = i;
	}
	int Log2[N], Min[N][35];
	inline void get_height() {
		for(int i = 1, j = 0; i <= n; ++i) {
			if(j) j -- ;
			while(s[i + j] == s[sa[rk[i] - 1] + j]) ++ j;
			height[rk[i]] = j;
		}
	}
	inline void Init(int len, int *data) {
	    for(int i = 2; i <= len; ++i) Log2[i] = Log2[i >> 1] + 1;
	    for(int i = 1; i <= len; ++i) Min[i][0] = data[i];
	    for(int j = 1; (1 << j - 1) <= len; ++j) {
	    	for(int i = 1; i + (1 << j - 1) <= len; ++i) {
	    		Min[i][j] = min(Min[i][j - 1], Min[i + (1 << j - 1)][j - 1]);
			}
		}
	}
	inline int getMin(int l, int r) {
		int k = Log2[r - l + 1];
		return min(Min[l][k], Min[r - (1 << k) + 1][k]);
	}
	inline int LCP(int posx, int posy) {
		if(posx == posy) return n - posx + 1;
		if(rk[posx] > rk[posy]) swap(posx, posy);
		return getMin(rk[posx] + 1, rk[posy]);
	}
	inline void cal() {
		get_sa(); get_height(); Init(n, height);
	}
};
SA ans;
struct Tree {
	int minn;
}tr[N];
inline void pushup(int u) {tr[u].minn = min(tr[u << 1].minn, tr[u << 1 | 1].minn);}
inline void build(int u, int x, int y) {
	if(x == y) {
		tr[u].minn = ans.rk[x];
		return ;
	}
	int mid = (x + y) >> 1;
	build(u << 1, x, mid), build(u << 1 | 1, mid + 1, y);
	pushup(u);
}
int query(int u, int x, int y, int a, int b, int k) {
	if(x > b || y < a) return 0;
	int mid = (x + y) >> 1;
	if(x == y) return tr[u].minn < k ? x : -1;
	if(a <= x && b >= y) {
		if(tr[u].minn < k) {
			if(tr[u << 1].minn < k) return query(u << 1, x, mid, a, b, k);
			else return query(u << 1 | 1, mid + 1, y, a, b, k);
		}
		else return -1;
	}
	if(a > mid) return query(u << 1 | 1, mid + 1, y, a, b, k);
	else {
		int tmp = query(u << 1, x, mid, a, b, k);
		if(tmp == -1) return query(u << 1 | 1, mid + 1, y, a, b, k);
		else return tmp;
	}
}
void solve() {
	cin >> ans.n >> ans.s;
	ans.s = " " + ans.s;
	ans.get_sa();
	ans.n ++ ;
	ans.rk[ans.n] = 0;
	build(1, 1, ans.n);
	for(int i = 1; i < ans.n; ++i) {
		int tmp = query(1, 1, ans.n, i + 1, ans.n, ans.rk[i]);
		cout << tmp - i << " ";
	}
	cout << '\n';
}
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while(T -- ) {
		solve();
	}
	return 0;
}
/*
1
3
aab
*/