#include<cstdio>
#include<cstring>
#define dim 1000009
using namespace std;
int nr,t,k,a[dim];
char v[dim];
void pref(int x)
{
    int k=0;
    a[1]=0;
    for(int i=2;i<=x;++i)
    {
        while(k>0&&v[k+1]!=v[i])
        k=a[k];
        if(v[k+1]==v[i])
        k++;
        a[i]=k;
        if((i-a[i]==a[i])||(i-a[i]==a[i]-a[a[i]]&&v[a[i]]))
        nr=i;
    }
}
int main()
{
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    scanf("%ld",&t);
    for(int i=1;i<=t;i++)
    {
        scanf("%s",v+1);
        v[0]='a';
        k=strlen(v)-1;
        v[0]=0;
        pref(k);
        printf("%ld\n",nr);
    }
}