#include <fstream>
#include <string>
#include <cstring>
using namespace std;

int const maxm=1000*1000+10;
char p[maxm+10];
int b[maxm+1],m,s;

void kmpPreprocess()
{	s=0;	
	int i=0,j=-1;
	b[i]=j;
	while(i<m)
	{	while((j>=0)&&(p[i]!=p[j])){j=b[j];}
		i++;j++;
		b[i]=j;
		if((2*j>=i)&&(0==(i%(i-j)))){s=i;}
	}
}

int main()
{	ifstream is("prefix.in");
	ofstream os("prefix.out");
	int T;is>>T;
	is.getline(p,maxm);
	while(0<T)
	{	--T;
		is.getline(p,maxm);
		m=strlen(p);
		kmpPreprocess();
		os<<s<<endl;
	}
	return 0;
}