#include<stdio.h>
#include<string.h>
int pi[1000001];
char s[1000001];
int main(){
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);
	int x,t,i,q;
	scanf("%d\n",&t);
	while(t){
		--t;
		fgets(s+1,1000001,stdin);
		x=0;
		q=0;
		for(i=2;s[i]!='\0';++i){
			while(q>0&&s[q+1]!=s[i])
				q=pi[q];
			if(s[q+1]==s[i])
				++q;
			pi[i]=q;
			if(pi[i]){
				if(pi[i]%(i-pi[i])==0){
					x=i;
				}
			}
		}
		printf("%d\n",x);
	}
	return 0;
}