#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("prefix.in");
ofstream fout("prefix.out");
char S[1000001];
int pref[1000001],t;
int maxi;
void kmp(char S[])
{
    int n=strlen(S);
    int j=0;
    for(int i=1;i<n;i++)
    {
        while(j!=0 && S[j+1]!=S[i]) j=pref[j];
        if(S[j+1]==S[i])
            j++;
        pref[i]=j;
        maxi=max(maxi,j);
    }
}
int main()
{
    int t;
    fin>>t;
    for(int i=1;i<=t;i++)
    {
        fin>>S;
        maxi=0;
        kmp(S);
        fout<<maxi<<"\n";
    }
    return 0;
}