#include<stdio.h>
#include<string.h>
#include<fstream>
using namespace std;
ifstream cin("prefix.in");
char s[1000005];
int n,p[1000005];
int main()
{
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    int n,i,t;
    scanf("%d",&n);cin>>(s+1);
    for(t=1;t<=n;t++)
    {
        cin>>(s+1);
        int x;
        p[0]=0;x=0;
        for(i=2;s[i]!=0;i++)
        {
            while(x && s[i]!=s[x+1])
                x=p[x];
            if(s[i]==s[x+1])
                x++;
            p[i]=x;
        }
        int max=0;
        for(i=1;s[i]!=0;i++)
            if(p[i]!=i && i%(i-p[i])==0 && p[i])
                max=i;
        printf("%d\n",max);
    }
    return 0;
}