约定：( ext{suf}(i))表示以(i)开头的后缀（(s[idots n])），( ext{pre}(i))表示以(i)结尾的前缀（(s[1dots i])），( ext{lcp}(s_1,s_2))表示两个串的最长公共前缀，( ext{lcs}(s_1,s_2))表示两个串的最长公共后缀。
设(f[i])表示以(i)为结尾的，( ext{AA})式的子串数量。(g[i])表示以(i)为开头的，( ext{BB})式的子串数量。我们可以枚举( ext{AA})与( ext{BB})的分界点，然后求出答案，也就是说，答案等于：
对每个(i)，都求一遍(f)和(g)。利用哈希或后缀数组判断子串相等。时间复杂度(O(n^2))，期望得(95)分。
继续优化。(f), (g)是类似的，以求(f)为例。考虑枚举( ext{A})的长度( ext{len})。我们把(1dots n)中所有是( ext{len})的倍数的点，标为“关键点”。发现一个( ext{AA})式的子串，必定跨过恰好(2)个关键点！
考虑一组相邻的关键点(i,j) （显然，(j=i+ ext{len})），计算跨过(i,j)的( ext{AA})的数量。设(x= ext{lcp}( ext{suf}(i), ext{suf}(j)))，(y= ext{lcs}( ext{pre}(i-1), ext{pre}(j-1)))。如果(x+y< ext{len})，显然跨过(i,j)的( ext{AA})数量为(0)。否则，中间的两段(x), (y)会有一个交，第一个( ext{A})的终点，只要落在这段交上都是可行的，所以会有(x+y- ext{len}+1)个跨过(i,j)的( ext{AA})，并且它们的结尾位置，是一段连续的区间，所以对这段区间的(f)值(+1)即可，可以用差分实现。
预处理后缀数组后，求( ext{lcp}), ( ext{lcs})可以(O(1))实现。因为关键点的总数是调和级数的，所以总时间复杂度(O(nlog n))。
参考代码：
//problem:LOJ2083
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}
const int MAXN=3e4;
const int LOG_MAXN=15;
int n;
char s[MAXN+5];
struct SuffixArray{
int n,m,x[MAXN+5],y[MAXN+5],c[MAXN+5],sa[MAXN+5];
int rk[MAXN+5],ht[MAXN+5],st[MAXN+5][LOG_MAXN+5];
int _log2[MAXN+5];
void clear(){
for(int i=1;i<=max(n,(int)'z');++i)c[i]=0;
for(int i=1;i<=n;++i)y[i]=0;
}
void init(){
_log2[0]=-1;
for(int i=1;i<=MAXN;++i)_log2[i]=_log2[i>>1]+1;
}
void build(char* s,int _n){
n=_n;
m='z';
for(int i=1;i<=n;++i)c[x[i]=s[i]]++;
for(int i=1;i<=m;++i)c[i]+=c[i-1];
for(int i=n;i>=1;--i)sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;++i)y[++num]=i;
for(int i=1;i<=n;++i)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=1;i<=m;++i)c[i]=0;
for(int i=1;i<=n;++i)c[x[i]]++;
for(int i=1;i<=m;++i)c[i]+=c[i-1];
for(int i=n;i>=1;--i)sa[c[x[y[i]]]--]=y[i];
for(int i=1;i<=n;++i)swap(x[i],y[i]);
x[sa[1]]=1;num=1;
for(int i=2;i<=n;++i)
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;
m=num;
}
for(int i=1;i<=n;++i)rk[sa[i]]=i;
//for(int i=1;i<=n;++i)cout<<rk[i]<<" ";cout<<endl;
int k=0;
for(int i=1;i<=n;++i){
if(rk[i]==1)continue;
if(k)--k;
int j=sa[rk[i]-1];
while(i+k<=n && j+k<=n && s[i+k]==s[j+k])
++k;
ht[rk[i]]=k;
}
for(int i=1;i<=n;++i)st[i][0]=ht[i];
for(int j=1;j<=LOG_MAXN;++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 rmq(int l,int r){
int k=_log2[r-l+1];
return min(st[l][k],st[r-(1<<k)+1][k]);
}
int get_lcp(int i,int j){
if(i==j)
return n-i+1;
i=rk[i]; j=rk[j];
if(i>j)swap(i,j);
assert(i<j);
return rmq(i+1,j);
}
SuffixArray(){}
};
SuffixArray SA,SA_rev;
int f[MAXN+5],g[MAXN+5];
void solve_case(){
SA.clear();
SA_rev.clear();
cin>>(s+1); n=strlen(s+1);
SA.build(s,n);
reverse(s+1,s+n+1);
SA_rev.build(s,n);
for(int i=1;i<=n;++i)f[i]=g[i]=0;
int maxlen=(n-2)/2;
for(int len=1;len<=maxlen;++len){
for(int k=1;(k+1)*len<=n;++k){
int i=k*len;
int j=(k+1)*len;
int lcp=SA.get_lcp(i,j);
int lcs=(i==1?0:SA_rev.get_lcp(n-(i-1)+1,n-(j-1)+1));
if(!lcp)continue;
int l=j-min(lcs,len-1)+len-1;
int r=min(n,j+min(lcp,len)-1);
if(l<=r){
f[l]++;f[r+1]--;
}
l=max(1,i-min(lcs,len-1));
r=i+min(lcp,len)-1-len+1;
if(l<=r){
g[l]++;g[r+1]--;
}
}
}
for(int i=1;i<=n;++i)f[i]+=f[i-1],g[i]+=g[i-1];
f[n+1]=g[n+1]=0;
ll ans=0;
for(int i=1;i<=n-2;++i)
ans+=(ll)f[i]*g[i+1];
cout<<ans<<endl;
}
int main() {
SA.init();
SA_rev.init();
int T;cin>>T;while(T--){
solve_case();
}
return 0;
}