#include<stdio.h>
#include<string.h>

#define lg 1000005

int teste, n, i, dif, urm[lg];
char sir[lg];

void prefix(){
	int k = 0, i;
	
	for (i = 2; i <= n; i ++){
		while (k > 0 && sir[k+1] != sir[i])
			k = urm[k];
		if (sir[k+1] == sir[i])
			k ++;
		urm[i] = k;
	}
}
bool check(int val){
	if (val == dif)
		return true;
	if (val - urm[val] != dif)
		return false;
	
	return check(urm[val]);
}
int main()
{
	freopen("prefix.in", "rt", stdin);
	freopen("prefix.out", "wt", stdout);
	
	scanf("%d\n", &teste);
	while (teste --){
		scanf("%s", sir+1);
		n = strlen(sir+1);
		
		memset(urm, 0, sizeof(urm));
		prefix();

		for (i = n; i; i --){
			dif = i - urm[i];
			
			if (check(urm[i])){
				printf("%d\n", i);
				break;
			}
		}
		if (!i)
			printf("0\n");
	}
	
	return 0;
}