0pts qt

#include<bits/stdc++.h>
using namespace std;
int cnt=1,p[25000050],ans;
char s[25000050];
void read(){
	char c=getchar();
	if(c<'a'||c>'z')c=getchar();
	s[1]='$';
	while(c>='a'&&c<='z'){
		s[++cnt]=c;
		s[++cnt]='$';
		c=getchar();
	}
}
signed main(){
	int t;
	cin>>t;
	while(t--){
		read();
		ans=0;
		int n=cnt;
		int r=0,m=0;
		for(int i=1;i<=n;i++){
			int k=2*m-i;
			if(i>r)p[i]=1;
			else p[i]=min(p[k],r-i+1);
			while(i-p[i]>=0&&i+p[i]<=n&&s[i+p[i]]==s[i-p[i]])p[i]++;
			if(p[i]+i-1>r) r=p[i]+i-1,m=i;
			ans=max(ans,p[i]-1);
		}
		memset(s,0,sizeof s);
		memset(p,0,sizeof p);
		cnt=1;
		cout<<ans<<endl;
	}
	return 0;
}```