#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+5;
int p[N<<2];
char s[N];
char c[N<<2];
int main(){
	int t;
	scanf("%d",&t);
	while(t --){
		int ans = -1;
		scanf("%s",&s);
		int n = strlen(s);
		c[0] = '@';
		for(int i=1;i<=n*2+1;i++){
			if(i&1){
				c[i] = '#';
			}else{
				c[i] = s[(i>>1)-1];
			}
		}
		p[1] = 1;
		for(int i=2,l,r=0;i<=n*2+1;i++){
			if(i <= r){
				p[i] = min(p[r+l-i],r-i+1);
			}
			while(c[i-p[i]] == c[i+p[i]]){
				p[i] ++;
			}
			if(i+p[i]-1 > r){
				r = i+p[i]-1;
				l = i-p[i]+1;
			}
			ans = max(ans,p[i]);
		}
		printf("%d\n",ans-1);
	}
}