#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)/2)
#define eb emplace_back
const int N=5e5+5,M=1e7+5,N1=1e3+5;
int T,n,f[N],g[N],w[N],f1[N1][N1];char a[N];
struct Point {int len,link,ch[26];};
int cnts;struct Seg {int ch[2];}sg[M];
int New() {sg[++cnts]=(Seg) {{0,0}};return cnts;}
int tot;
void upd(int &p,int l,int r,int x)
{
	tot++;
    if(!p) p=New();if(l==r) return;
    if(x<=mid) upd(sg[p].ch[0],l,mid,x);
    else upd(sg[p].ch[1],mid+1,r,x);
}
int merge(int pl,int pr)
{
	tot++;
    if(!pl || !pr) return pl+pr;
    int p=++cnts;
    sg[p].ch[0]=merge(sg[pl].ch[0],sg[pr].ch[0]);
    sg[p].ch[1]=merge(sg[pl].ch[1],sg[pr].ch[1]);
    return p;
}
bool qry(int p,int l,int r,int ql,int qr)
{
	tot++;
    if(!p || l>qr || r<ql || ql>qr) return 0;
    if(l>=ql && r<=qr) return 1;
    return qry(sg[p].ch[0],l,mid,ql,qr) || qry(sg[p].ch[1],mid+1,r,ql,qr);
}
struct SuffixAutoMaton
{
    int n,nw,cntp,o[N],d[N],rt[N],fa[20][N];
    bool vs[N];vector<int> e[N];Point pt[N];
    SuffixAutoMaton() {nw=cntp=1;}
    void clear()
    {
        n=0;
        for(int i=1;i<=cntp;++i)
        {
            pt[i].len=pt[i].link=o[i]=d[i]=rt[i]=vs[i]=0;
            fill(pt[i].ch,pt[i].ch+26,0);e[i].clear();
        }
        nw=cntp=1;
    }
    void ext(int w)
    {
        int p=nw,p1,t;pt[nw=++cntp].len=pt[p].len+1;
        o[++n]=nw;vs[nw]=1;
        while(p && !pt[p].ch[w]) pt[p].ch[w]=nw,p=pt[p].link;
        if(!p) {pt[nw].link=1;return;}p1=pt[p].ch[w];
        if(pt[p].len+1==pt[p1].len) {pt[nw].link=p1;return;}
        pt[t=++cntp]=pt[p1];pt[t].len=pt[p].len+1;
        while(p && pt[p].ch[w]==p1) pt[p].ch[w]=t,p=pt[p].link;
        pt[nw].link=pt[p1].link=t;
    }
    void dfs(int u,int f)
    {
        fa[0][u]=f;rt[u]=0;d[u]=d[f]+1;
        for(int i=1;i<=19;++i) fa[i][u]=fa[i-1][fa[i-1][u]];
        for(auto v:e[u]) dfs(v,u),rt[u]=merge(rt[u],rt[v]);
        if(vs[u]) upd(rt[u],1,n,pt[u].len);
    }
    int find(int u,int x)
    {
        for(int i=__lg(d[u]);i>=0;--i)
            if(pt[fa[i][u]].len>=x) u=fa[i][u];
        return u;
    }
    void build()
    {for(int i=2;i<=cntp;++i) e[pt[i].link].eb(i);dfs(1,0);}
    bool chk(int l,int r,int l1,int r1)
    {
		tot++;
        int t=find(o[r],r-l+1);
        return qry(rt[t],1,n,l1+r-l,r1);
    }
}SAM;
void slv()
{
    SAM.clear();cnts=0;
    scanf("%s",a+1);n=strlen(a+1);
    if(n<=30)
    {
        for(int i=n;i;--i) for(int j=i;j<=n;++j)
        {
            int t=i;
            while(t<j && a[t]==a[i+j-t]) ++t;
            f1[i][j]=max({f1[i+1][j],f1[i][j-1],(i<t?f1[i][t-1]+1:0)});
        }
        printf("%d\n",f1[1][n]);
        return;
    }
    for(int i=1,t=0;i<=n;++i)
        if(i==n || a[i]!=a[i+1])
        {for(int j=i;j>t;--j) w[j]=i-t;t=i;}
    for(int i=1;i<=n;++i) SAM.ext(a[i]-'a');
    for(int i=n;i;--i) SAM.ext(a[i]-'a');
    SAM.build();
    for(int i=1;i<=n;++i) f[i]=n;
    int ans=0;
    for(int x=1;x<=19;++x)
    {
        for(int i=2;i<=n;++i) f[i]=max(f[i],f[i-1]);
        fill(g+1,g+n+1,0);
        for(int i=1,t=0;i<=n;++i)
        {
            t=max(t-2,0);if(i>f[i] || f[i]-i+x-1<ans) continue;
            while(t<f[i]-i && SAM.chk(i,i+t,n*2-f[i]+1,n*2-i)) ++t;
            if(t==f[i]-i)
            {
                int t1=min(w[(i+f[i])/2],f[i]-i+1);
                ans=max(ans,(f[i]-i+1-t1)/2+t1-1+x-1);
            }
            else g[i]=max(g[i],i+t-1);
        }
        copy(g+1,g+n+1,f+1);
        for(int i=1;i<=n;++i) if(i<=f[i]) ans=max(ans,x);
    }
    printf("%d\n",ans);
}
int main()
{
    scanf("%d",&T);
    while(T--) slv();
	std::cerr<<tot<<std::endl;
    return 0;
}