#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define input "prefix.in"
#define output "prefix.out"
using namespace std;

const int nMax = 1e6 + 13;
char a[nMax];
int n, pi[nMax], k, q, ans;


main()
{
    ifstream cin(input);
    ofstream cout(output);

    cin >> q;
    for (; q; --q)
    {
        cin >> a + 1;
        n = strlen(a + 1);
        k = 0;

        for (int i = 2; i <=n; ++i)
        {
            while (k && a[i] != a[k + 1])
                k = pi[k];
            if (a[i] == a[k + 1])
                ++k;
            pi[i] = k;
            if (pi[i] != 0  && pi[i] % (i - pi[i]) == 0)
                ans = i;
        }
    cout << ans << "\n";
    }
}