#include<iostream>
#include<fstream>
#include<cstring>
#include<windows.h>
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;
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;
        }
        cout<<nr;
        system("PAUSE");
        x=x+NB;
        a=a+NB;
    }
    if(k!=0)
    {
        cmp();
    }
    else
    {
        if(nr==0 && NB!=0)
        {
            NB--;
            hashB();
            x=NB;
            a=0;
        }
        if(nr!=0)
        {
            a=NA+1;
           // return 0;
        }
        if(NB==0)
        {
            a=NA+1;
         //   return 0;
        }
    }
}
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;
            a=0;

            while(NB!=0 && nr==0)
            {
                hashB();
                cmp();
            }
            if(NB==0 && nr==0)
            {
                fout<<"0"<<endl;
            }
            if(nr!=0)
            {
                nr=nr+NB;
                fout<<nr<<endl;
            }
        }
    }
    fin.close();
    fout.close();
    return 0;
}