#include <stdio.h>
#include <string.h>

#define MAXL 1000500
#define MAXT 15

int teste=0;
int pi[MAXL],nV=0;

//note: elementele sirului de caractere incep de pe pozitia 1
char v[MAXL];


void calcpi()
{
	int k=0,i;
	pi[1]=0;
	for (i=2; i<=nV; ++i)
	{
		while (k>0 && v[k+1]!=v[i])
			k=pi[k];
		if (v[k+1]==v[i])
			++k;
		pi[i]=k;
	}
}

int calcpref(int N)
{
	int k=0,i,l=N;
	for (i=N+1; i<=nV; ++i)
	{
		while (k>0 && v[k+1]!=v[i])
			k=pi[k];
		if (v[k+1]==v[i])
			++k;
		if (k==N)
		{
			k=0;
			if (i%N==0)
				l+=N;
			else
				if (l==N)
					return 0;
				else
					return l;
		}
		else
			if (i%N==0)
				if (l==N)
					return 0;
				else
					return l;
	}
	return l;
}


void rezolvare()
{
	int rez=0,i,k;
	
	memset(pi,0,sizeof(pi));
	calcpi();
	
	for (i=1; i<nV/2+1; i++)
	{
		k=calcpref(i);
		if (k>rez)
			i=rez=k;
	}
	printf("%d\n",rez);
}


void rezolva()
{
	char s[10]; int i=0;
	
	teste=0;
	
	fgets(s,10,stdin);
	
	while (s[i]>='0' && s[i]<='9')
		teste=teste*10+s[i++]-'0';
	
	for (i=0; i<teste; i++)
	{
		fgets(v+1,MAXL,stdin);
		nV=strlen(v+1);
		while (!(v[nV]>='a' && v[nV]<='z'))
			nV--;
		
		rezolvare();
	}	
}

int main()
{
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);
	
	rezolva();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}