#include <bits/stdc++.h>
#define NMAX 10005

using namespace std;

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

int t, pi[NMAX],b[NMAX];


int main()
{
    fin >> t;

    while(t--)
    {
        char a[NMAX];
        int ans, n, k;
        fin >> a+1;
        n = strlen(a+1);
        k = ans = 0;
        for(int i = 0; i <= n; i++)
            b[i] = pi[i] = 0;
        for(int i = 2; i <= n; i++)
        {
            while(k && a[k+1] != a[i])
                k = pi[k];
            if(a[k+1] == a[i])
                k++;
            pi[i] = k;

            if(b[k]!=-1 && k && (i-k)%k == 0)
             {
                 if((i-k)/k == b[k]+1)
                    b[k]++, ans = max(ans, i), k=0;
                else
                    b[k] = -1;
             }

        }
        fout << ans << '\n';
    }
    return 0;
}