#include <iostream>
#include <cstdio>

using namespace std;

char text[1000002];
int pre_suf[1000002];

void clear(int n)
{
    for(int k=0; k<=n; k++)
        pre_suf[k]=0;
}

int main()
{
    int z;
    string input;

    cin >> z;
    for(int x=1; x<=z; x++)
    {
        cin >> input;

        int d=input.length();
        clear(d);
        for(int i=0; i<d; i++)
            text[i+1]=input[i];

        int counter=0;
        for(int i=2; i<=d; i++)
        {
            while(counter>0 && text[i]!=text[counter+1])
                counter=pre_suf[counter];
            if(text[i]==text[counter+1])
                counter++;
            pre_suf[i]=counter;
        }

        for(int i=0; i<=d; i++)
            cout << pre_suf[i] << " ";
        cout << endl;
    }

    system("pause");
    return 0;
}