#include<iostream>
#include<iomanip>
#include<cmath>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
const int bn=32000005;
char exs[bn],s[bn];
int d[bn];
inline void edit(const char* s){
	int len = strlen(s);
	int k=0;
	exs[0]='$';
	exs[++k]='#';//要形成形如"$#a#b#c#d#\0"这种字符才行，保证必然是奇数个字符，必然对称
	for(int i=0;i<len;i++){
		exs[++k]=s[i];exs[++k]='#';
	}
	exs[++k]='\0';
}
void solve(){
    scanf("%s", s);
    edit(s);
	int nlen=strlen(exs);
	int l=0,r=0,symi=0;d[0]=0;d[1]=1;
	int maxv=d[1];
	for(int i=2;i<nlen;i++){
		if(l<=i&&i<=r) symi=l+r-i,d[i]=min(d[symi],r-i+1);//因为d[i]的回文半径也是加了1的，这里也要补齐，从它本身开始计算回文半径ji
		while(exs[i+d[i]]==exs[i-d[i]]) d[i]++;
		if(l>i-d[i]+1) r=i+d[i]-1, l=i-d[i]+1; //更新盒子的长度，在盒子里面的都可以直接用对称原理求得
		if(d[i]>maxv){
			maxv=d[i];
		}
	}
	printf("%d\n",maxv-1);
}
int main() {
	//ios::sync_with_stdio(false);
	int t;cin>>t;
	while(t--){
		solve();	
	}
	
    return 0;
}

大佬们，我已经尽我所能在优化了，但是还是TLE，我不知道那里出问题了