#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],maxi;
void mp()
{
    int poz=0,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;
        if(p[i]==i-p[i] || ok[p[i]]==i-p[i])
        {
            ok[i]=i-p[i];
            maxi=i;
        }
    }
}
int main()
{
    int n,i,j,k,poz,aux,nr;
    fin>>n;
    for(k=1;k<=n;k++)
    {
        fin>>(s+1);
        ls=strlen(s+1);
        poz=0;
        maxi=0;
        memset(ok,0,sizeof(ok));
        mp();
        fout<<maxi<<"\n";
    }
}