#include <cstdio>
#include <cstring>

using namespace std;

char v[1000010];
int t,n,sol,a[1000001];

int main()
{
    int i,j,l;
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    scanf("%d\n",&t);
    v[0]=' ';
    for (i=1;i<=t;++i)
    {
        l=1;a[1]=0;sol=0;
        for (j=1;j<=1000009;++j)
        {
            v[j]=NULL;
            a[j]=0;
        }
        fgets(v+1,1000005,stdin);
        n=strlen(v)-2;
        for (j=2;j<=n;++j)
        {
            if (v[j]==v[j-l]&&(a[j-1]+1==l||j==n||v[j+1]==v[j+1-l]))
                a[j]=a[j-1]+1;
            else
            {
                l=j;
                a[j]=0;
            }
            if (a[j]==l)
            {
                a[j]=0;
                sol=j;
            }
        }
        printf("%d\n",sol);
    }
    return 0;
}