#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

ifstream f ("prefix.in");
ofstream g ("prefix.out");

constexpr int NMAX = 1e6 + 5;

char a[NMAX+5];

int phi[NMAX+5];
int N;

void Construiesc_KMP ()
{
    int rez = 0;
    for (int i = 1; i < N; ++ i )
    {
        while (rez > 0 && a[ rez ] != a[ i ])
        {
            rez = phi[ rez - 1 ];
        }
        if (a[ rez ] == a[ i ])
            ++ rez;
        phi[ i ] = rez;
    }
}

int main ()
{
    int T;
    f >> T;
    f.get();

    for (; T; --T)
    {
        f.getline(a, NMAX);
        N = strlen(a);
        Construiesc_KMP();
        int sol = 0;
        for (int i = 0; i < N; ++i)
            if ( (i + 1) - phi[ i ] < i + 1 && (i + 1) % ((i + 1) - phi[ i ]) == 0) {
                sol = i+1;
            }
        g << sol << '\n';
    }

    return 0;
}