#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
using namespace std;
char s[1000006];
int nt,it,mij,mij2,dr,dr2,coresp,equiv,i,z[1000006],mx,l,sz;
int main(void)
{
    FILE * f;
    f=fopen("prefix.in","r");
    ofstream g("prefix.out");
    fscanf(f,"%d",&nt);
    fgets(s,1000002,f);
    for (it=1;it<=nt;it++)
    {
        fgets(s,1000002,f);
        memset(z,0,sizeof(z));
        sz=strlen(s);
        s[sz]='*';
        mx=0;
        mij=dr=-1;
        for (i=1;i<sz;i++)
        {
            if (i>=dr)
            {
                mij=i;
                dr=i;
                coresp=0;
                while (s[dr]==s[coresp])
                {
                    dr++;
                    coresp++;
                }
                dr--;
                z[i]=coresp;
            }
            else
            {
                mij2=i;
                equiv=i-mij;
                dr2=min(dr,i+z[equiv]);
                coresp=dr2-mij2;

                while (s[dr2]==s[coresp])
                {
                    dr2++;
                    coresp++;
                }
                z[i]=coresp;
                if (dr2>dr)
                {
                    dr=dr2;
                    mij=mij2;
                }
            }
            if (z[i]>=i)
            {
                l=i+z[i]-z[i]%i;
                if (l>mx)
                    mx=l;
            }
        }
        g<<mx<<'\n';
    }
    g.close();
    return 0;
}