RT，样例1第二个没过，输出 $3$

#include<bits/stdc++.h>
#define mid (l+(r-l>>1))
#define ls mid<<1
#define rs mid<<1|1
using namespace std;
const int N=1e5+5;
int T,len,n,st[N],ed[N];
long long ans;
string s;
struct SAM{
	struct node{
		int fa,len,s[26];
	}nd[N];
	struct edge{
		int v,nxt;
	}egs[N];
	int tot,lst,head[N],ei;
	int dep[N],sz[N],a[N];
	int top[N],son[N];
	inline void add(int u,int v){
		egs[++ei]={v,head[u]};head[u]=ei;
	}
	inline void extend(short c){
		int fa=lst,u=lst=++tot;nd[u].len=nd[fa].len+1;
		for(;fa&&!nd[fa].s[c];fa=nd[fa].fa)nd[fa].s[c]=u;
		if(!fa)nd[u].fa=1;else{int q=nd[fa].s[c];
			if(nd[q].len==nd[fa].len+1)nd[u].fa=q;
			else{
				int nq=++tot;nd[q].fa=nd[u].fa=nq;
				nd[nq]=nd[q],nd[nq].len=nd[fa].len+1;
				for(;fa&&nd[fa].s[c]==q;fa=nd[fa].fa)
					nd[fa].s[c]=nq;
			}
		}
	}
	inline void dfs1(int u){
		dep[u]=dep[nd[u].fa]+1,sz[u]=1;
		for(int i=head[u];i;i=egs[i].nxt){
			const int v=egs[i].v;
			if(!(v^nd[u].fa))continue;
			dfs1(v),sz[u]+=sz[v];
			if(sz[son[u]]<sz[v])son[u]=v;
		}
	}
	inline void dfs2(int u){
		if(!son[u])return;
		top[son[u]]=top[u],dfs2(son[u]);
		for(int i=head[u];i;i=egs[i].nxt){
			const int v=egs[i].v;
			if(v^nd[u].fa&&v^son[u])dfs2(top[v]=v);
		}
	}
	inline int LCA(int u,int v){
		u=a[u],v=a[v];
		while(top[u]^top[v]){
			if(dep[top[u]]<dep[top[v]])
				swap(u,v);u=nd[top[u]].fa;
		}return dep[u]<dep[v]?u:v;
	}
	inline void init(){
		tot=lst=1;ei=0;
		memset(nd,0,sizeof(nd));
		memset(egs,0,sizeof(egs));
		memset(head,0,sizeof(head));
	}
	inline void solve(string s){
		init();
		for(int i=1; i<=n; ++i)a[n-i+1]=tot+1,extend(s[i]-'a');
		for(int i=2; i<=tot; ++i)add(nd[i].fa,i);
		dfs1(1),dfs2(1);
	}
}Pre,Suf;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;while(T--){
		memset(st,0,sizeof(st));
		memset(ed,0,sizeof(ed));
        cin>>s;n=s.size();s='&'+s;Pre.solve(s);
		reverse(s.begin()+1,s.end());Suf.solve(s);
		for(int ln(1),x,y; ln<=(n>>1); ++ln){
			for(int l=ln,r=l+ln; r-1<=n; l+=ln,r+=ln){
				x=y=0;
				if(l>1)x=min(Pre.nd[Pre.LCA(l-1,r-1)].len,ln-1);
				if(r<=n)y=min(Suf.nd[Suf.LCA(n-l+1,n-r+1)].len,ln);
				if(x+y<ln)continue;
				++st[l-x],--st[l+y-ln+1];
				++ed[r+ln-x],--ed[r+y+1];
			}
		}
		st[1]+=st[0],ed[1]+=ed[0],st[2]+=st[1],ed[2]+=ed[1];
		for(int i=2; i<n-1; ++i){
			st[i+1]+=st[i],ed[i+1]+=ed[i];
			ans+=1ll*ed[i]*st[i+1];
		}cout<<ans<<'\n';
    }
	return 0;
}