#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin ("prefix.in");
ofstream fout("prefix.out");
int i,NA,NB,N,a,x,k,nr,r;
int hashB1,hashB2,hashA1,hashA2,j,nrmax,cp;
char B[500009],A[1000009];
#define MOD1 100007
#define MOD2 100021
#define P 73
void hashB()
{
    hashB1=hashB2=0;
    for(i=0;i<NB;i++)
    {
        hashB1=(hashB1*P+B[i])%MOD1;
        hashB2=(hashB2*P+B[i])%MOD2;
    }
}
void cmp()
{
    k=0;
    hashA1=hashA2=0;
    for(i=a;i<x && x<=NA;i++)
    {
        hashA1=(hashA1*P+A[i])%MOD1;
        hashA2=(hashA2*P+A[i])%MOD2;
    }
    if(hashB1==hashA1 && hashB2==hashA2)
    {
        k++;
        if(a!=0)
        {
            nr=nr+NB;
        }
        x=x+NB;
        a=a+NB;
    }
    if(k!=0)
    {
        cmp();
    }
    else
    {
        if(NB!=0 && nr==0)
        {
            NB--;
            hashB();
            x=NB;
            a=0;
        }
        if(nr!=0)
        {
            if(nr>nrmax)
            {
                nrmax=nr;
                cp=NB;
            }
            NB--;
            hashB();
            x=NB;
            a=0;
            nr=0;
        }
        if(NB<=0)
        {
            a=NA+1;
        }
    }
}
int main ()
{
    fin>>N;
    for(j=1;j<=N;j++)
    {
        fin.get();
        fin.get(A,1000009);
        NA=strlen(A);
        if(NA==1)
        {
            fout<<"0"<<endl;
        }
        else
        {
            r=NA/2;
            strncpy(B,A,r);
            B[r]=0;
            NB=strlen(B);
            nr=0;
            x=NB+NB;
            a=NB;
            nrmax=0;
            cp=0;

            while(NB!=0)
            {
                hashB();
                cmp();
            }

            if(NB==0 && nrmax==0)
            {
                fout<<"0"<<endl;
            }
            if(nrmax!=0)
            {
                nrmax=nrmax+cp;
                fout<<nrmax<<endl;
            }
        }
    }
    fin.close();
    fout.close();
    return 0;
}