#include <bits/stdc++.h>

#define N_MAX 1000002

using namespace std;

int t;

int n;

string s1, s;

int kmp[N_MAX], per[N_MAX];

int main()
{
    ifstream fin ("prefix.in");
    ofstream fout ("prefix.out");
    fin >> t;
    while(t--)
    {
        fin >> s;
        n = s.size();
        kmp[1] = 0;
        per[1] = 1;
        int mx = 0;
        for(int i = 2; i <= n; i++)
        {
            kmp[i] = kmp[i - 1];
            while(kmp[i] > 0 && s[kmp[i] + 1 - 1] != s[i - 1])
                kmp[i] = kmp[kmp[i]];
            if(s[kmp[i] + 1 - 1] == s[i - 1])
                kmp[i]++;
            if(kmp[i] > 0 && 2 * kmp[i] >= i && i % per[kmp[i]] == 0)
                per[i] = per[kmp[i]];
            else
                per[i] = i;
            if(per[i] != i)
                mx = i;
        }
        fout << mx << "\n";
    }
    return 0;
}