#include<iostream>
#include<fstream>
#include<cstring>
#define DX 1000010
using namespace std;
fstream fin("prefix.in",ios::in),fout("prefix.out",ios::out);
char s[DX];
int p[DX],ls,ok[DX];
void mp()
{
    int poz,i;
    for(i=2;i<=ls;i++)
    {
        while(poz!=0 && s[poz+1]!=s[i]) poz=p[poz];
        if(s[poz+1]==s[i]) poz++;
        p[i]=poz;
    }
}
int main()
{
    int n,i,j,k,poz,aux,nr,maxi;
    fin>>n;
    for(k=1;k<=n;k++)
    {
        fin>>(s+1);
        ls=strlen(s+1);
        mp();
        poz=0;
        maxi=0;
        memset(ok,0,sizeof(ok));
        for(i=2;i<=ls;i++)
        {
            if(p[i]==i-p[i] || ok[p[i]]==i-p[i])
            {
                ok[i]=i-p[i];
                maxi=i;
            }
        }
        cout<<maxi<<"\n";
    }
}