#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);
        ans = 0;
        k = 0;
        pi[1] = 0;
        for (int i = 2; i <= n; ++i)
        {
            while (k > 0 && a[i] != a[k + 1])
                k = pi[k];

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