#include<cstdio>
#include<string.h>
int ;
int main()
{
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    scanf("%d",&h);
    for(l=1;l<=h;l++)
    {
        gets(x+1);
        n=strlen(x+1);
        k=0;
        p[1]=0;
        for(i=2;i<=n;i++)
        {
            while(k>0&&x[i]!=x[k+1])
            {
                k=p[k];
            }
            if(x[i]==x[k+1]) k++;
            p[i]=k;
        }
        for(i=k;i>=1;i--)
        {
            //if(p[i])
        }
    }
    return 0;
}