#include <fstream>
#include <string>

using namespace std;

ifstream mama("prefix.in");
ofstream tata("prefix.out");

short int T;
int v[1000001];
int n;
string S;

int prefix(int q)
{
    int l,r=0,maxi=0;
    for(int k=1,aux,j;k<=n/2 and r<q;k++)
    {
        l=k; aux=k;
        for(int i=k;i<n and r<q;i++)
        {
            j=0;
            if(k>1)
                {
                    if(S[i]==S[j])
                        {
                            while(j<k and i<n and S[i+1]==S[j+1])
                            {
                                i++;
                                j++;
                                if(S[i]==S[0]) r++;
                            }

                        }

                if(j<k-1) {k=v[++r]-1; i=n;}
                    else {l=l+k; i--;}
                }
                else
            if(k==1)
            {
                while(S[i]==S[j])
                {
                    i++;
                    r++;
                }
                if(i>1)
                    {
                        l=i;
                        k=v[r]-1;
                    }
                    i=n;
            }
        }
        if(l>aux and l>maxi) maxi=l;
    }
    return maxi;
}
int main()
{
    mama>>T;
    for(int i=1,j,k;i<=T;i++)
    {
        mama>>S;
        n=S.size();
        v[0]=0; k=0; j=0;
        while(j<n-1)
            if(S[++j]==S[0]) v[++k]=j;
        tata<<prefix(k)<<'\n';
        }
    return 0;
}