#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 >> s1;
        s = " ";
        s += s1;
        n = s.size() - 1;
        kmp[1] = 0;
        per[1] = 1;
        for(int i = 2; i <= n; i++)
        {
            kmp[i] = kmp[i - 1];
            while(kmp[i] > 0 && s[kmp[i] + 1] != s[i])
                kmp[i] = kmp[kmp[i]];
            if(s[kmp[i] + 1] == s[i])
                kmp[i]++;
            if(kmp[i] > 0 && i % per[kmp[i]] == 0 && 2 * kmp[i] >= i)
                per[i] = per[kmp[i]];
            else
                per[i] = i;
        }
        int mx = 0;
        for(int i = 1; i <= n; i++)
            if(per[i] != i)
                mx = i;
        fout << mx << "\n";
    }
    return 0;
}