#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 ok=0;
        for(i=strlen(s+1);i;i--)
            if(p[i]!=i && i%(i-p[i])==0 && p[i])
            {printf("%d\n",i);ok=1;break;}
        if(ok==0) printf("0\n");
    }
    return 0;
}