#include<stdio.h>
#define Nmax 1000010
#define IN "prefix.in"
#define OUT "prefix.out"

int maxp,t;
char c[Nmax];
int pi[Nmax];

void prefix()
{
	int k=0;
	pi[1]=0;
	maxp=0;
	for(int i=2;c[i]!='\0';++i)
	{
		while ( (k>0) && (c[k+1]!=c[i]) )
			k=pi[k];
		if(c[i]==c[k+1])
			k++;
		pi[i]=k;
		if(pi[i]!=0)
			if(pi[i]%(i-pi[i])==0)
				maxp=i;
		}
	}
int main()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d\n",&t);
	
	for(int ti=1;ti<=t;++ti)
	{
		fgets(c+1,1000010,stdin);  
        prefix();  
        printf("%d\n",maxp); 
	}	 
	return 0;
}