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

#define MAXL 1000500
#define MAXT 15

int teste=0;
int pi[MAXL],nV=0,d;
//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 findpref(int k)
{
	
	if (k==d)
		return 0;
	if (k-pi[k]==d)
		return findpref(pi[k]);
	return 1;
}

void rezolvare()
{
	int rez=0,i,k;
	
	memset(pi,0,sizeof(pi));
	calcpi();
	
	for (i=nV; i>=1; i--)
	{
		d=i-pi[i];
		if(pi[i])
		{
			k=findpref(i);
			if (!k)
			{
				rez=i;
				i=0;
			}
		}
	}
	
	printf("%d\n",rez);
}


void readnsolve()
{
	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);
	
	readnsolve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}