#include <iostream>
#include <cstring>
#define FIN "prefix.in"
#define FOUT "prefix.out"
#define MAX 1000010
using namespace std;
int T;
char S[MAX];
int pi[MAX],pik[MAX],valid[MAX],Len;


void iofile(void){

		freopen(FIN,"rt",stdin);
		freopen(FOUT,"wt",stdout);
		scanf("%d\n",&T);
		return ;
}


void prel(void){

	memset(pi,0,sizeof(pi));
	memset(pik,0,sizeof(pik));
	memset(valid,0,sizeof(valid));
	int res=0;
	int q=0;
	for (int i=2;i<=Len;++i){
		while (S[i]!=S[q+1] && q){q=pi[q];}
		if (S[i]==S[q+1]){++q;}
		pi[i]=q;
		if (2*pi[i]==i){valid[i]=1;pik[i]=pi[i];res=i;} else {
			if (valid[i-pik[pi[i]]]){valid[i]=1;pik[i]=pik[pi[i]];res=i;}
		}
	}
	printf("%d\n",res);
	return ;
}

void solve(void){

	for (int i=1;i<=T;++i){
		fgets(S+1,MAX-2,stdin);
		Len=strlen(S+1);
		while (S[Len]=='\n'){--Len;}
		prel();
	}
	fclose(stdin);
	fclose(stdout);
	return ;
}


int main(void){

	iofile();
	solve();
	return 0;
}