#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
int phi[1000002];
void prefix(char *s,long size)
{
	long i,k;
	k=0;
	phi[1]=0;
	for(i=2;i<=size;++i)
	{
		while(k>0 && s[k+1]!=s[i])
			k=phi[k];
		if(s[k+1]==s[i]) ++k;
		phi[i]=k;
	}
}
int main()
{
	ifstream f("prefix.in");
	ofstream g("prefix.out");
	char s[2000003];
	char c;
	int t,j;
	long i,n,max=-1,maxpos,dif,pos;
	f>>t;
	f.get(c);
	for(j=1;j<=t;++j)
	{
		max=-1;
		f.getline((s+1),2000004);
		n=strlen(s+1);
		prefix(s,n);
		for(i=1;i<=n;++i)
		{
			if(phi[i]>max)
			{
				max=phi[i];
				maxpos=i;
			}
		}
		if(max==0 || max==1) g<<0<<"\n";
		else
		{
			while(maxpos<2*(maxpos-phi[maxpos])) maxpos=maxpos-phi[maxpos]-1;
			dif=maxpos-phi[maxpos];
			if(dif==0) g<<maxpos<<"\n";
			else g<<dif*(maxpos/dif)<<"\n";
		}
	}
	f.close();
	g.close();
	return 0;
}