#include <iostream>
#include <fstream>
#include <string.h>
int T, i, l, rez, prim, ultim, pl, j, x;
char str [1000001];
int match[1000001];
using namespace std;
void kmp_match()
{
    match[0]=0;
    int j=0;
    for(i=1;i<l;++i)
    {
        while(j>0 && (str[i]!=str[j]))
            j=match[j-1];

        if(str[i]==str[j])
            ++j;
        match[i]=j;
    }
}
int main ()
{
    ifstream in ("prefix.in");
    ofstream out ("prefix.out");
    in>>T;
    for(int c=0;c<T;++c)
    {
        for(i=0;i<1000002;++i)
        {
            str[i]=0;
            match[i]=0;
        }
        //in.getline(str, 1000001, "\n");
        in>>str;
        //cout<<str<<endl;
        l=strlen(str);
        kmp_match();
        cout<<endl;
        for(int k=0;k<l;++k)
            cout<<match[k]<<" ";
        cout<<endl;
        rez=0;
        i=1;
        while(i<l)
        {
            if(match[i]*2==i+1)
            {
                j=i;
                x=match[i];
                while(j<l && match[j]==x)
                {
                    ++x;
                    ++j;
                }
                x=(j/match[i])*match[i];
                if(x>rez)
                    rez=x;
                i=j;
            }
            else
                ++i;

        }
        out<<rez<<"\n";
    }
    in.close();
    out.close();
    return 0;
}