#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("prefix.in");
ofstream fout("prefix.out");

char s[1000002];
int pi[1000002],fr[1000002];
int n,maxv,k,t;

int main()
{
    fin>>t;

    for (;t; --t)
    {
        fin>>(s+1);

        n = strlen(s+1);

        pi[1] = 0;
        fr[1] = 1;
        k = 0;
        maxv = 0;

        for (int i=2; i<=n; ++i)
        {
            while (s[i]!=s[k+1] && k != 0)
                k = pi[k];

            if (s[i]==s[k+1])
                ++k;

            pi[i] = k;

            if (i-k == fr[k])
            {
                fr[i] = fr[k];
                maxv = i;
            }
            else fr[i] = i;
        }

        fout<<maxv<<"\n";
    }
}