hash被卡…
本来以为是回文自动机裸题
发现fail树上一条链的节点表示的回文子串的中点是不一样的…
不过回文树上的链是一样的

那么用建出回文树（我用回文自动机建的，manacher建不知道为什么WA了），然后找到以每个点为中点的最大回文子串，这个用manacher找

在对应节点加上贡献就行了

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef unsigned long long ull;
typedef long long ll;const int N=1000010,P1=19980403,P2=998244353,base1=131,base2=129;int t,n,p,cnt=1,nxt[N][30],fa[N],len[N],fail[N],val[N];
char a[N];ull hs1[N],pw1[N],hs2[N],pw2[N];struct Hst{int G[P1+10],nxt[N<<1],pos[N<<1],cnt;ull val[N<<1];void clear(){ memset(G,0,sizeof(G)); cnt=0; }void insert(ull x,int p){ull u=x>>32,v=x-(u<<32);//for(int i=G[u];i;i=nxt[i])//  if(val[i]==x) return ;++cnt; val[cnt]=v; nxt[cnt]=G[u]; G[u]=cnt; pos[cnt]=p;}int find(ull x){ull u=x>>32,v=x-(u<<32);for(int i=G[u];i;i=nxt[i])if(val[i]==v) return pos[i];}
}H;inline ull Getsub(int l,int r){ull a=(hs1[r]+P1-hs1[l-1]*pw1[r-l+1]%P1)%P1;ull b=(hs2[r]+P2-hs2[l-1]*pw2[r-l+1]%P2)%P2;return a<<32|b;
}inline void extend(int c,int ps){while(a[ps-len[p]-1]!=a[ps]) p=fail[p];if(!nxt[p][c]){int np=++cnt,k=fail[p]; len[np]=len[p]+2;while(a[ps-len[k]-1]!=a[ps]) k=fail[k];fail[np]=nxt[k][c]; fa[np]=p;nxt[p][c]=np;H.insert(Getsub(ps-len[np]+1,ps),np);}p=nxt[p][c];
}char b[N<<1];int r[N<<1];inline void manacher(){int t=0;for(int i=1;i<=n;i++)b[++t]=a[i],b[++t]='%';int mxr=0,p=0;for(int i=1;i<=t;i++){int j=0;if(i<=mxr)j=min(i+r[2*p-i],mxr+1);j=max(j,i+1);while(2*i-j>0 && j<=t && b[2*i-j]==b[j]) j++;r[i]=j-i;int L=i-r[i]+1,R=i+r[i]-1;if(b[L]=='%') L++,R--;if(L<=R) val[H.find(Getsub(L+1>>1,R+1>>1))]^=(i+1>>1)-1;if(i+r[i]-1>mxr) mxr=i+r[i]-1,p=i;}
}inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}inline void read(int &x){char c=nc(); x=0;for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}inline int read(char *a){char c=nc(); int x=0;for(;c>'z'||c<'a';c=nc());for(;c>='a'&&c<='z';a[++x]=c,c=nc()); return x;
}int main(){read(t);while(t--){n=read(a); cnt=1; p=0;memset(nxt,0,sizeof(nxt));memset(val,0,sizeof(val));H.clear();len[1]=-1; fail[0]=fail[1]=1; pw1[0]=pw2[0]=1;for(int i=1;i<=n;i++){hs1[i]=(1LL*hs1[i-1]*base1+a[i])%P1,pw1[i]=1LL*pw1[i-1]*base1%P1;hs2[i]=(1LL*hs2[i-1]*base2+a[i])%P2,pw2[i]=1LL*pw2[i-1]*base2%P2;}for(int i=1;i<=n;i++) extend(a[i]-'a',i);int ans=0;manacher();for(int i=cnt;i;i--) val[fa[i]]^=val[i];for(int i=2;i<=cnt;i++) ans=max(ans,val[i]);printf("%d\n",ans);}return 0;
}