第 13 个点本机没问题，提交re。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=z;x>=y;x--)
#define LL long long
using namespace std;
const int N=3e4+10;
int n,m;
LL g[N],f[N];//f[i]±íʾÒÔj½áβµÄAA´®¸öÊý+1 (i<=j<=n) 
struct SA
{
	int sa[N],x[N],y[N],c[N],rk[N],height[N];
	int st[N][25];
	char s[N];
	void get_sa()
	{
		m=26;
		memset(c,0,sizeof(c));
		memset(rk,0,sizeof(rk));
		memset(sa,0,sizeof(sa));
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(height,0,sizeof(height));
		rep(i,1,n) c[x[i]=s[i]-'a'+1]++;
		rep(i,2,m) c[i]+=c[i-1];
		per(i,1,n) sa[c[x[i]]--]=i;
		for(int k=1;k<=n;k<<=1)
		{
			int num=0;
			rep(i,n-k+1,n) y[++num]=i;
			rep(i,1,n) if(sa[i]>k) y[++num]=sa[i]-k;
			rep(i,1,m) c[i]=0;
			rep(i,1,n) c[x[i]]++;
			rep(i,2,m) c[i]+=c[i-1];
			per(i,1,n) sa[c[x[y[i]]]--]=y[i],y[i]=0;
			swap(x,y);
			x[sa[1]]=num=1;
			rep(i,2,n) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
			if(num==n) break;
			else m=num;
		}
	}
	void get_height()
	{
		rep(i,1,n) rk[sa[i]]=i;
		int k=0;
		rep(i,1,n)
		{
			if(k) k--;
			int j=sa[rk[i]-1];
			while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k]) k++;
			height[rk[i]]=k;
		}
	}
	void get_st()
	{
		memset(st,0,sizeof(st));
		rep(i,1,n) st[i][0]=height[i];
		for(int j=1;j<=20;j++)
			for(int i=1;i+(1<<j)-1<=n;i++)
				st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
	}
	int LCP(int a,int b)//st±íÇóÇø¼ä×îСֵ£¬¸ù¾Ýlcp(i,j)=min{lcp(i,k),lcp(k,j)} (i<k<=j) 
	{
		if(a>n||b>n) return 0;
		int l=rk[a],r=rk[b];
		if(l>r) swap(l,r);
		l++;
		int k=log2(r-l+1);
		return min(st[l][k],st[r-(1<<k)+1][k]);
	}
}a,b;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		scanf("%s",a.s+1);
		n=strlen(a.s+1);
		rep(i,1,n) b.s[n-i+1]=a.s[i];
		a.get_sa();
		b.get_sa();
		a.get_height();b.get_height();//a·­×ªµÃµ½b£¬ÓÃÀ´ÇóÁ½¸öǰ׺µÄ×¹«¹²ºó׺ 
		a.get_st();b.get_st();
		for(int len=1;len<=n/2;len++)
		{
			for(int l=len;l<=n;l+=len)
			{
				int r=l+len;
				int lcp=min(len,a.LCP(l,r));
				int lcs=min(len-1,b.LCP(n-r+2,n-l+2));//aµÄµÚi¸öºó׺ÊÇbµÄµÚn-(i-1)+1¸öºó׺ 
				if(lcp+lcs>=len)//[l,l+lcp-1]ºÍ[r-lcs+1,r]¿ÉÒÔÁ¬ÆðÀ´ 
				{
					int cov=lcp+lcs-len+1;//[l,l+lcp-1]ºÍ[r-lcs+1,r]½»¼¯µÄ´óС 
					f[r+lcp-cov]++,f[r+lcp]--;//¸øÇø¼ä[r+lcp-1+(cov+1),r+lcp-1]¼Ó1 
					g[l-lcs]++,g[l-lcs+cov]--;
				}
			}
		}
		rep(i,1,n) f[i]+=f[i-1],g[i]+=g[i-1];
		LL ans=0;
		rep(i,1,n-1) ans+=f[i]*g[i+1];
		printf("%lld\n",ans);
	}
	return 0;
}