#include <iostream>
#include <cstdio>
#include <cstring>
#define Nmax 1000010
using namespace std;

int N;
char S[Nmax];
int P[Nmax];
int Max;
int Poz;

void Rezolvare()
{
    int Lg=strlen(S);
    int q=0;
    for(int i=2;i<Lg;++i)
    {
        while(q && S[q+1]!=S[i])
            q=P[q];
        if(S[q+1]==S[i])
            q++;
        P[i]=q;
        if(P[i]>Max)
        {
            Max=P[i];
            Poz=i;
        }
    }
}


void Afisare()
{
    for(int i=1;i<strlen(S);++i)
        printf("%d ",P[i]);
    printf("\n");
}


int main()
{
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    scanf("%d",&N);
    for(int contor=0;contor<N;++contor)
    {
        scanf("%s\n",S+1);
        S[0]='0';
        memset(P,0,sizeof(P));
        Max=Poz=0;
        Rezolvare();
        //Afisare();
        printf("%d\n",Poz);
    }
    return 0;
}