#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 410000;
const int maxp = 100005*60;
const int maxc = 27;

struct segment
{
	int tot;
	int seg[maxp],lc[maxp],rc[maxp];
	void init()
	{
		tot=0;
	}
	int newnode()
	{
		++tot;
		seg[tot]=lc[tot]=rc[tot]=0;
		return tot;
	}
	int loc,c;
	int ins(const int x,const int l,const int r)
	{
		int y=newnode();
		lc[y]=lc[x],rc[y]=rc[x];
		seg[y]=seg[x]+1;
		if(l!=r)
		{
			int mid=(l+r)>>1;
			if(loc<=mid) lc[y]=ins(lc[y],l,mid);
			else rc[y]=ins(rc[y],mid+1,r);
		}
		return y;
	}
	int findnex(const int x,const int y,const int l,const int r) //find > loc
	{
		if(seg[y]-seg[x]==0 || r<=loc) return 0;
		if(l==r) return l;
		const int mid = (l+r)>>1;
		
		int ret=findnex(lc[x],lc[y],l,mid);
		if(!ret) ret=findnex(rc[x],rc[y],mid+1,r);
		return ret;
	}
}seg;
int segroot[maxn];

struct PAM
{
	int S[maxn];
	int son[maxn][maxc],fail[maxn],len[maxn],f[maxn];
	int tot,last;
	void init(string str) 
	{
		int n=str.size();
		
		S[0]=-1; for(int i=1;i<n;i++) S[i]=str[i]-'a';
		
		tot=1,last=0;
		memset(son[0],0,sizeof son[0]);
        memset(son[1],0,sizeof son[1]);
		fail[0]=1,fail[1]=0;
		len[0]=0,len[1]=-1;
		f[0]=f[1]=0;
    }
	int newnode(int l) 
	{
		tot++;
		memset(son[tot],0,sizeof son[tot]);
		len[tot]=l,fail[tot]=0;
		return tot;
	}
	pair<int,int> extend(const int i) 
	{
		int p=last,w=S[i],np;
		while(S[i-1-len[p]]!=w) p=fail[p];
		if(!son[p][w]) {
			np=newnode(len[p]+2);
			int t=fail[p];
			while(S[i-1-len[t]]!=w) t=fail[t];
			fail[np]=son[t][w];
			son[p][w]=np;
			
			f[np]=max(f[p]+1,f[fail[np]]+1);
		}
		else np=son[p][w];
		last=np;
		
		return make_pair(f[np],len[np]);
	}
}pam;			//	1-base ,S[0] ��Ҫ�� S ���ַ�����һ��

vector< vector<int> >E;
int ff[maxn][20],trL[maxn];
int siz[maxn],dfn[maxn],idfn[maxn],dfi;
void dfs(const int x)
{
	siz[x]=1;
	dfn[x]=++dfi; idfn[dfi]=x;
	
	for(int i=1;i<20;i++) ff[x][i]= ff[ ff[x][i-1] ][i-1];
	for(auto y:E[x]) 
	{
		ff[y][0]=x;
		dfs(y);
		siz[x]+=siz[y];
	}
}
int jump(int x,int boundL) //find x: trL[par[x]]<boundL
{
	for(int i=19;i>=0;i--) if( trL[ff[x][i]]>=boundL)
		x=ff[x][i];
	return x;
}
struct SAM //��S match T�������Ӵ�����failʱҪ����ά����ǰ����len������ֱ����len[p]
{
	int rt,tot,last;
	int son[maxn][maxc],par[maxn],len[maxn],pos[maxn];
	int newnode() {
		++tot;
		memset(son[tot],0,sizeof son[tot]);
		par[tot]=0; len[tot]=0; pos[tot]=0;
		return tot;
	}
	void init() {
		rt=tot=0;
		rt=newnode();
		
		last=rt;
	}
	int extend(const int w,const int j) {
		int p=last, np=newnode();
		len[np]=len[p]+1;
		
		while(p && !son[p][w]) son[p][w]=np,p=par[p];
		if(!p) par[np]=rt;
		else {
			int q=son[p][w];
			if(len[q]==len[p]+1) par[np]=q;
			else {
				int nq=newnode();
				memcpy(son[nq],son[q],sizeof son[q]);
				len[nq]=len[p]+1;
				par[nq]=par[q];
				par[np]=par[q]=nq;
				
				while(p && son[p][w]==q) son[p][w]=nq, p=par[p];
			}
		}
		last=np;
		pos[np]=j;
		
		return last;
	}
	void build()
	{
		E.resize( tot+5 );
		for(int i=1;i<=tot;i++) 
		{
			if(par[i]) E[par[i]].emplace_back(i);
			trL[i]=len[i];
		}
		
		dfi=0; ff[rt][0]=0; dfs(rt);
	}
}sam;

string str,Rstr;
int n;
int f[maxn],leni[maxn];
int samid[maxn];

int main() 
{
	ios_base::sync_with_stdio(false);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		{
			vector< vector<int> >_;
			E.swap(_);
		}
		
		cin>>str; n=str.size();
		Rstr=str; reverse(Rstr.begin(),Rstr.end());
		
		str=' '+str;
		Rstr=' '+Rstr;
		
		pam.init(Rstr);
		for(int i=1;i<=n;i++) tie(f[n-i+1],leni[n-i+1])= pam.extend(i);
		
		sam.init();
		for(int i=1;i<=n;i++) samid[i]= sam.extend(str[i]-'a',i);
		for(int i=1;i<=n;i++) samid[n+i]= sam.extend(str[n-i+1]-'a',n+i);
		sam.build();
		
		seg.init();
		segroot[0]=0;
		for(int i=1;i<=dfi;i++)
		{
			int x= idfn[i];
			if(sam.pos[x])
			{
				seg.loc=sam.pos[x],seg.c=1;
				segroot[i]=seg.ins(segroot[i-1],1,2*n);
			}
			else segroot[i]=segroot[i-1];
		}
		
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			int temp= f[i], len= leni[i];
			
			while(1)
			{
				int x= jump( samid[n+n-i+1],len );
				seg.loc= i+len-1;
				int nex= seg.findnex( segroot[dfn[x]-1],segroot[dfn[x]+siz[x]-1],1,2*n);
				if(nex==0 || nex>n) break;
				temp++;
				len= nex-i+1;
			}
			
			ans=max(ans,temp);
		}
		
		cout<<ans-1<<'\n';
	}
	
    return 0;
}