#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

int n, pi[1000010], lg;
char a[1000010];

inline void kmp()
{
    int k = 0, i;
    pi[1] = 0;
    for (i = 2; i<=lg; i++)
    {
        while (k && a[k+1] != a[i])
            k = pi[k];
        if (a[k+1] == a[i])
            k++;
        pi[i] = k;
    }
}

int main()
{
    ifstream f("prefix.in");
    ofstream g("prefix.out");
    f>>n;
    int i;
    bool gasit;
    while (n--)
    {
        f>>(a+1);
        lg = strlen(a+1);
        kmp();
        gasit = false;
        for (i=lg; i && !gasit; i--)
        {
            if (pi[i] && i%(i-pi[i]) == 0)
            {
                g<<i<<"\n";
                gasit = true;
            }
        }
        if (!gasit)
            g<<"0\n";
    }
    f.close();
    g.close();
    return 0;
}