#include<bits/stdc++.h>
using namespace std;

const int NMAX=1000010;

int prevv[NMAX];
char s[NMAX];

int prefix(){
	int k=0,rez=0,n=strlen(s+1);
	for(int i=2;i<=n;i++){
		while(k>0 && s[k+1]!=s[i])
			k=prevv[k];
		if(s[k+1]==s[i])
			k++;
		prevv[i]=k;
		if(prevv[i] && prevv[i]%(i-prevv[i])==0)
            rez=i;
	}
	return rez;
}

int main(){
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);
	int t;
	scanf("%d", &t);
	for(int i=1;i<=t;i++){
		scanf("%s", s+1);
		printf("%d\n", prefix());
	}
	return 0;
}