#include <iostream>
#include <cstring>
#include <fstream>
int lp,lt,k,i,urm[1000000];
char t[1000000],p[1000000];
using namespace std;
ifstream f("prefix.in");
ofstream g("prefix.out");
void prefix()
{
    int i;
    k=0;
    urm[1]=0;
    for(i=2;i<=lt;++i)
    {
        while(k>0&&t[i]!=t[k+1])
    k=urm[k];
    if(t[i]==t[k+1])
        ++k;
    urm[i]=k;
    }
}
int n,j,poz;
int main()
{
    f>>n;
    f.get();
    for(i=1;i<=n;++i)
    {
        f.getline(t,1000000);
        lt=strlen(t);
        for(j=lt;j>0;--j)
            t[j]=t[j-1];
        prefix();
        poz=0;
        for(j=1;j<=lt;++j)
            if(urm[j]&&j%(j-urm[j])==0)
            poz=j;
        g<<poz<<'\n';
    }
    return 0;
}