#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;
}