#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int N=4e5+5;
int T, n;
char s[N];

struct SAM{
	int len[N], fa[N], ch[N][26];
	int cnt, lst;
	int rt[N], idx;
	int pos[N];
	int gen(){
		++idx;
		occ[idx]=false; ls[idx]=rs[idx]=0;
		return idx;
	}
	int f[N][20];
	bool occ[N*60]; int ls[N*60], rs[N*60];
	void ins(int &p, int l, int r, int x){
		if(!p) p=gen();
		occ[p]=true;
		if(l==r) return ;
		int mid=(l+r)>>1;
		if(x<=mid) ins(ls[p], l, mid, x);
		else ins(rs[p], mid+1, r, x);
	}
	int merge(int p, int q, int l, int r){
		if((!p)||(!q)) return p+q;
		int np=gen();
		if(l==r){
			occ[np]=occ[p]|occ[q];
			return np;
		}
		int mid=(l+r)>>1;
		ls[np]=merge(ls[p], ls[q], l, mid);
		rs[np]=merge(rs[p], rs[q], mid+1, r);
		occ[np]=occ[ls[np]]|occ[rs[np]];
		return np;
	}
	void extend(int c, int lim){
		int p=lst, np=lst=++cnt;
		if(lim<=n) ins(rt[np], 1, n, lim);
		pos[lim]=np;
		len[np]=len[p]+1;
		for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=np;
		if(!p) fa[np]=1;
		else {
			int q=ch[p][c];
			if(len[q]==len[p]+1) fa[np]=q;
			else{
				int nq=++cnt;
				for(int i=0; i<26; ++i) ch[nq][i]=ch[q][i];
				fa[nq]=fa[q];
				len[nq]=len[p]+1;
				fa[q]=fa[np]=nq;
				for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
			}
		}
	}
	vector<int> e[N];
	void init(){
		for(int i=1; i<=cnt; ++i) {
			for(int c=0; c<26; ++c) ch[i][c]=0;
			fa[i]=len[i]=rt[i]=0;
			e[i].clear();
			for(int t=0; t<20; ++t) f[i][t]=0;
		}
		cnt=lst=1; idx=0;
	}
	void dfs(int x){
		for(int y:e[x]) {
			f[y][0]=x;
			for(int i=1; f[y][i-1]; ++i) f[y][i]=f[f[y][i-1]][i-1];
			dfs(y); 
			rt[x]=merge(rt[x], rt[y], 1, n);
		}
	}
	void merge(){
		for(int i=2; i<=cnt; ++i) e[fa[i]].ep(i);
		dfs(1);
	}
	int locate(int l, int r){
		int x=pos[r];
		for(int t=19; t>=0; --t) if(len[f[x][t]]>=r-l+1) x=f[x][t];
		return x;
	}
	int get(int p, int l, int r, int L, int R){
		if(!occ[p]) return 0;
		if(L<=l&&r<=R){
			if(l==r) return l;
			int mid=(l+r)>>1;
			if(occ[rs[p]]) return get(rs[p], mid+1, r, L, R);
			else return get(ls[p], l, mid, L, R);
		}
		int mid=(l+r)>>1, ret=0;
		if(R>mid) ret=get(rs[p], mid+1, r, L, R);
		if(ret==0&&L<=mid) ret=get(ls[p], l, mid, L, R);
		return ret;
	}
}S;
struct PAM{
	int ch[N][26], fail[N], len[N];
	int lst, cnt;
	void init(){
		for(int x=0; x<=cnt; ++x) {
			fail[x]=len[x]=0;
			for(int i=0; i<26; ++i) ch[x][i]=0;
		}
		len[0]=0; len[1]=-1;
		fail[0]=1; fail[1]=0;
		lst=0; cnt=1;
	}
	int get_fail(int x, int lim){
		while(s[lim-len[x]-1]!=s[lim]) x=fail[x];
		return x;
	}
	void insert(int c, int lim){
		int p=get_fail(lst, lim);
		if(!ch[p][c]){
			++cnt;
			len[cnt]=len[p]+2;
			int q=get_fail(fail[p], lim);
			fail[cnt]=ch[q][c];
			ch[p][c]=cnt;
		}
		lst=ch[p][c];
	}
}P;
int jmp[N];
bool flag=0; int cnt=0;
void solve(){
	scanf("%s", s+1);
	++cnt;
	if(flag&&cnt==242) {
		printf("%s\n", s+1);
		exit(0);
	}
	if(flag) return ;
	n=strlen(s+1);
	S.init();
	for(int i=1; i<=n; ++i) {
		S.extend(s[i]-'a', i);
		if(s[i]==s[i-1]) jmp[i]=jmp[i-1]+1;
		else jmp[i]=1;
	}
	for(int i=n; i>=1; --i) S.extend(s[i]-'a', 2*n+1-i);
	S.merge();
	P.init();
	int mxans=0;
	for(int i=1; i<=n; ++i){
		P.insert(s[i]-'a', i);
		int len=P.len[P.lst];
		// printf("%d %d\n", i, len);
		int ans=0;
		if(len&1){
			int mid=i-len/2;
			int cont=jmp[mid]-1;
			ans=cont*2+len/2-cont;
		}
		else{
			int mid=i-len/2;
			int cont=jmp[mid];
			ans=cont*2-1+len/2-cont;
		}
		// printf("working:%d\n", i);
		int l=i-len+1;
		while(true){
			// printf("%d %d\n", l, i);
			if(l-1<i-l+1) break;
			int node=S.locate(2*n+1-i, 2*n+1-l);
			int nxtl=S.get(S.rt[node], 1, n, 1, 2*l-i-1);
			if(nxtl==0) break;
			l=nxtl;
			++ans;
		};
		mxans=max(mxans, ans);
	}
	printf("%d\n", mxans);
}
int main(){
	// freopen("D:\\nya\\acm\\A\\test.in","r",stdin);
	// freopen("D:\\nya\\acm\\A\\test.out","w",stdout);
	read(T);
	if(T==500) flag=1;
	while(T--) solve();
	return 0;
}