#include <bits/stdc++.h>

using namespace std;

ifstream in("prefix.in");
ofstream out("prefix.out");
string sir;
int t, pref[1000001];
long long rk[1000001], putere[1000001], A = 915359133, B = 974328597;

int cmmdc(int a, int b)
{
    while(b)
    {
        int rest = a%b;
        a = b;
        b = rest;
    }

    return a;
}

int valRK(int st, int dr)
{
    return (rk[dr] - rk[st-1] * putere[dr-st+1] + B*B) % B;
}

int main()
{
    in >> t;

    while(t--)
    {
        in >> sir;
        sir = " " + sir;
        int sol = 0;

        for(int i = 2, lung = 0; i < sir.size(); i++)
        {
            while(lung && sir[lung+1] != sir[i])
                lung = pref[lung];

            if(sir[lung+1] == sir[i])
                lung++;

            pref[i] = lung;
        }

        putere[0] = 1;

        for(int i = 1; i < sir.size(); i++)
        {
            rk[i] = (rk[i-1]*A + sir[i]) % B;
            putere[i] = (putere[i-1]*A) % B;
        }

        if(sir[1] == sir[2])
            sol = 2;

        for(int i = 3; i < sir.size(); i++)
            if(pref[i] >= i/2 && cmmdc(i, pref[i]) != 1 && valRK(1, i - pref[i]) == valRK(pref[i] + 1, i))
                sol = i;

        out << sol << '\n';
    }

    return 0;
}