#include <iostream>
#include <cstdio>
#include <cstring>
#define N 1000005

using namespace std;

int n, t, poz[N], nr;
char s[N];

struct
{
    int m, ind;
}maxim;

void prefix()
{
    int j=0;
    for(int i=2;i<=n;i++)
    {
        while(j && s[j+1]!=s[i])
            j=poz[j];
        if(s[j+1]==s[i])
            j++;
        if(j>maxim.ind)
            maxim.ind=j, maxim.m=i;
        poz[i]=j;
    }
}

int main()
{
    freopen("prefix.in", "r", stdin);
//    freopen("prefix.out", "w", stdout);
    scanf("%d\n", &t);
    for(int test=1;test<=t;test++)
    {
        fgets(s+1, N, stdin);
        n=strlen(s+1)-1;
        s[n+1]='\0';
        maxim.ind=maxim.m=0;
        memset(poz, 0, sizeof(poz));
        prefix();
        printf("%d\n", maxim.m);
    }
    return 0;
}