#include <cstdio>
#include <cstring>

FILE* in=fopen("prefix.in","r");
FILE* out=fopen("prefix.out","w");

const int Q=1000001;

char v[Q];
int size;

int pre[Q];
//int val[Q];

void rezolv()
{
    int k=0;
    int last=0;

    for(int i=2; i<=size; i++)
    {
        while(k>0 && v[i]!=v[k+1])
            k=pre[k];
        if(v[k+1]==v[i])
            k++;
        pre[i]=k;
/*
        if(k!=0 && i%(i-k)==0)
            last=i;
*/

        if(k*2==i)
        {
            val[i]=k;
            last=i;
        }
        else if(k!=0 && val[k]==i-k)
        {
            val[i]=val[k];
            last=i;
        }

    }
    fprintf(out,"%d\n",last);
}

int main()
{
    int t;

    fscanf(in,"%d\n",&t);

    for(int i=1; i<=t; i++)
    {
        fgets(v+1,Q,in);
        //fscanf(in,"%s\n",v+1);
        size=strlen(v+1);
        rezolv();
    }

    return 0;
}