#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int T,i,N,z[1000005];
char s[1000005];
int main()
{
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    scanf("%d\n",&T);
    while (T--)
    {
        gets(s+1); N=strlen(s+1);
        int L=1,R=1,pozmax=0;
        for (i=2;i<=N;i++)
        {
            if (R>=i) z[i]=min(z[i-L+1],R-i+1);
            for (;i+z[i]<=N && s[i+z[i]]==s[z[i]+1];z[i]++);
            if (i+z[i]-1>R) L=i,R=i+z[i]-1;
            if (z[i]>z[pozmax] && z[i]>=i-1) pozmax=i;
        }
        int j=pozmax;
        if (pozmax>0)
            while (z[j]>=pozmax-1)
                j+=pozmax-1;
        printf("%d\n",max(0,j-1));
        memset(z,0,sizeof(z));
    }
    return 0;
}