#include <stdio.h>
#include <string.h>
#define maxl 1000010

int i,j,x,n,t,prefix;
char sir[maxl];
int pref[maxl];

int main()
{
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    
    scanf("%d",&t);

    while (t)
    {
        t--;
        
        scanf("%s",sir+1);
        sir[0]=' ';
        n=strlen(sir)-1;
        
        for (i=1; i<=n; i++) pref[i]=0;
        
        x=0;
        for (i=2; i<=n; i++)
        {
            while (sir[x+1] != sir[i] && x) x=pref[x];
            if (sir[x+1]==sir[i]) 
            {
               pref[i]=x+1;
               x++;                  
            }
        }
        
		prefix=0;

		for (i=2; i<=n; i++)
			if (i/(i-pref[i])>1 && i-pref[i]>1)
			{
				prefix=i-pref[i];
				break;
			}

		if (prefix==0)
		{
            i=2;
            while (sir[i]==sir[1] && i<=n) i++;
            i--;
            if (i==1) printf("0\n");
            else printf("%d\n",i);
		}
		else
		{
			for (j=i+1; j<=n; j++)
				if (j/(j-pref[j])>1 && pref[j]<=pref[j+1]) continue;
				else break;
			j=j-j%prefix;
			printf("%d\n",j);
		 }
	}

	return 0;
}