/// https://www.infoarena.ro/automate-finite-si-kmp
#include <fstream>
#include <cstring>

using namespace std;

const int NMAX = 1e6 + 1;

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

char a[NMAX];
int n, m, pi[NMAX];

void calcPrefix()
{
    int x = 0;
    pi[1] = 0;
    for(int i = 2; i <= n; ++i)
    {
        while(x > 0 && a[x] != a[i - 1])
            x = pi[x];
        if(a[x] == a[i - 1])
            ++x;
        pi[i] = x;
    }
}

int potrivireKMP(int ind, int lg)
{
    int x = 0, nrap = 0;
    for(int i = 1; i <= lg; ++i)
    {
        while(x > 0 && a[x] != a[i - 1])
            x = pi[x];
        if(a[x] == a[i - 1])
            ++x;
        if(x == ind) /// Potrivire
        {
            ++nrap;
            x = pi[x];
        }
    }
    return nrap;
}

void solutie()
{
    fin >> a;
    n = strlen(a);
    calcPrefix();
    for(int i = n; i; --i)
    {
        if(!pi[i]) continue;
        int j = i - pi[i];
        int ap = potrivireKMP(j, i);
        if(i % j == 0 && potrivireKMP(j, i) >= i / j)
        {
            fout << i << "\n";
            return;
        }
    }
    fout << "0\n";
}

int main()
{
    int t;
    fin >> t;
    while(t--)
        solutie();
    return 0;
}