#include <bits/stdc++.h>

typedef long long lnt;

using namespace std;

const int N = 1e5 + 7;

int n;
char s[N];
int ne[N];

void INIT() { }

void WORK() {
    cin >> (s + 1);
    n = strlen(s + 1);
    for (int i = 2, j = 1; i <= n; ++ i) {
        while (j && s[j + 1] != s[i]) j = ne[j];
        if (s[j + 1] == s[i]) ++ j;
        ne[i] = j;
    }
    for (int i = 1; i <= n; ++ i) {
        cout << ne[i] << '\n';
    }
}

//#define filename ""

int main() {
    #ifdef filename
    freopen(filename ".in", "r", stdin);
    freopen(filename ".out", "w", stdout);
    #endif
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);		
    
    int Turn = 1;
    cin >> Turn;
    INIT();
    while (Turn -- ) {
        WORK();
    }
    return 0;
}