#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("prefix.in");
ofstream g("prefix.out");
char s[1000005];
int pi[1000005];
void KMP(int &n)
{
    n=1;
    int i,k=0;
    for(i=2;s[i];i++)
    {
        ++n;
        while(k and s[k+1]!=s[i])
            k=pi[k];
        if(s[k+1]==s[i]) ++k;
        pi[i]=k;
    }
    for(i=1;s[i];i++)
        s[i]=0;
}
int main()
{
    int T,i,n;
    bool ok;
    f>>T;
    f.get();
    for(;T;--T)
    {
        f.getline(s+1,1000005);
        KMP(n);
        ok=true;
        for(i=n;i;i--)
            if(pi[i] and !(pi[i]%(i-pi[i])))
            {
                g<<i<<'\n';
                i=1;
                ok=false;
            }
        if(ok) g<<0<<'\n';
    }

    return 0;
}