//pe baza ideii lui Florian Marcu fara KMP (vezi la comentarii)
#include <fstream>
#include <cstring>



int main(){
	std::ifstream fin("prefix.in");
	std::ofstream fout("prefix.out");

	int T; fin>>T; fin.get(); fin.get();
	while(T--){
		char s[1000002];
		fin>>(s+1);
		s[0]='!';
		const unsigned n=strlen(s)-1;

		unsigned sol=0; //solutia
		unsigned L=1; //lungimea perioadei
		unsigned nou=0,vechi=0; //cate caractereau fost adaugate

		for(unsigned i=1;i<=n;++i){
			if(s[i]==s[i-L]&&(i==n||s[i+1]==s[i+1-L]||vechi+1==L)) nou=vechi+1;
			else{
				nou=0;
				L=i;
			}
			if(nou==L){
				sol=i;
				nou=0;
			}
			vechi=nou;
		}

		fout<<sol<<'\n';
	}
}