#include<cstdio>
#include<string>
using namespace std;
#define MAX_N 1000003
char s[MAX_N];
int N;
void solve()
{
	int i, L, nou, vechi;
	int sol = 0;
	L = 1;
	s[0] = '!';
	N = strlen(s) - 1;
	for(i=1; i<=N; ++i)
	{
		if(s[i] == s[i-L] && (i==N || s[i+1] == s[i+1-L] || vechi + 1 == L)) nou = vechi + 1;
		else 
			{
			nou = 0; L = i;
			}
		if(nou == L) 
			{
				nou = 0;
				sol = i;
			}
		vechi = nou;
	}
	printf("%d\n",sol);
}
int main()
{
	int T;
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);
	scanf("%d\n",&T);
	while(T--)
	{
		memset(s,0,sizeof(s));
		scanf("%s\n",s+1);
		solve();
	}
	return 0;
}