#include <cstring>
#include <cstdio>

#define MAX_N	1000000
#define max(a,b) (a > b? a : b)

class Candidate 
{
public:
	int start;
	int current;
	Candidate():start(0),current(0){}
};

Candidate candidates1[MAX_N];
Candidate candidates2[MAX_N];
int goodLengths[MAX_N];
char sir[MAX_N],sir2[MAX_N];
int iMaxLengths = 0;

bool takeSir(char *input,char *output,int iBegin,int iLength)
{
	if ((iBegin+iLength) > (int)strlen(input))
		return false;

	for (int i=iBegin;i<iBegin+iLength;i++)
		output[i-iBegin] =	input[i];

	output[iLength]='\0';

	return true;
}

bool EqualyStrings(char *s,char *p)
{
	int length = strlen(s);
	if (length != strlen(p))
		return false;

	for (int i=0;i < length;i++)
		if (s[i] != p[i])
			return false;

	return true;
}

void longestPrefix(char *data)
{
	iMaxLengths = 0;
	int i_nrCandidatesNew=0,i_nrCandidatesLast=0;
	int iMaxim=0,i,j;
	int iDataLength = strlen(data);


	//introduce in the queue all initial pot
	if (iDataLength > 1 && data[0] == data[1])
		goodLengths[iMaxLengths++] = 1;

	for (i = 2;i <= iDataLength/2 ;i++)
		if (data[0] == data[i])
		{
			candidates1[i_nrCandidatesNew].start = i;
			candidates1[i_nrCandidatesNew].current = i;
			i_nrCandidatesNew ++ ;
		}

		while(i_nrCandidatesNew > 0)
		{
			i_nrCandidatesLast = 0;
			for (i = 0;i< i_nrCandidatesNew; i++)
			{
				int start = candidates1[i].start;
				int current = candidates1[i].current + 1;

				if (data[current - start] == data[current])
				{
					if ((current - start) == (start - 1) ) 
						goodLengths[iMaxLengths++] = start;
					else
					{
						candidates2[i_nrCandidatesLast].current = current;
						candidates2[i_nrCandidatesLast].start = start;
						i_nrCandidatesLast++;
					}
				}
			}
			memcpy(candidates1,candidates2,sizeof(candidates2));
			i_nrCandidatesNew = i_nrCandidatesLast;
		}

}
int findPrecs(char *data)
{
	int n = strlen(data);
	
	int maxDim = 0;

	for (int i = iMaxLengths - 1 ;i >= 0; i--)
	{

		int l = goodLengths[i];
		bool taken = takeSir(data,sir,0,l),bPeriodicyCanContinue;
		int indexLeft = 2*l;
		int nrTries = 2;

		if (taken)
			do
			{
				bPeriodicyCanContinue = false;
				taken = takeSir(data,sir2,indexLeft,l);
				if (taken)
				{
					indexLeft += l;
					if (bPeriodicyCanContinue = EqualyStrings(sir,sir2))
						nrTries++;
				}

			}while(bPeriodicyCanContinue);

			if (nrTries > 1)
				maxDim = max(maxDim,nrTries * l);

	}

	return  maxDim;
}

void solve()
{
	int n;
	scanf("%d",&n);
	char sir[MAX_N];
	for (int i=0;i<n;i++)
	{
		scanf("%s\n",&sir);
		longestPrefix(sir);
	//	printf("%d\n",findPrecs(sir));
	}
}



int main()
{
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);
	solve();

	return 0;
}