//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;
	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 bst=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]||bst+1==L)) ++bst;
			else{
				bst=0;
				L=i;
			}
			if(bst==L){
				sol=i;
				bst=0;
			}
		}

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