将问题转化为统计以 $i$ 结尾的 $AA$ 串个数.
我们将后缀树建出来，然后按照启发式合并的方式每次合并两个 $endpos$ 集合.
那么就有：$[x-mx,x-1] ightarrow x$ 与 $x ightarrow [x+1,x+mx]$ 的贡献.
统计第一种贡献的话在线段树上区间查询就行.
第二种贡献的话要在线段树上维护一个 lazy 标记（这个标记区别于线段树合并中的 $sum$)
然后将整颗后缀树合并完了后统计下传根节点的 $lazy$ 标记即可.
细节比较多.
code:
// NOI2016 优秀的拆分
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#define N 30002
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char S[N];
int n,bu[N],A[N],B[N];
namespace seg
{
#define lson s[x].ls
#define rson s[x].rs
int tot;
struct data
{
int ls,rs,sum,tag;
void clr() { ls=rs=sum=tag=0; }
}s[N*50];
int newnode() { return ++tot; }
void pushup(int x) { s[x].sum=s[lson].sum+s[rson].sum; }
void mark(int x,int v) { s[x].tag+=v; }
void pushdown(int x)
{
if(s[x].tag)
{
if(lson) mark(lson,s[x].tag);
if(rson) mark(rson,s[x].tag);
s[x].tag=0;
}
}
void update(int &x,int l,int r,int p,int v)
{
if(!x) x=newnode();
s[x].sum+=v;
if(l==r) return;
pushdown(x);
int mid=(l+r)>>1;
if(p<=mid) update(lson,l,mid,p,v);
else update(rson,mid+1,r,p,v);
}
int query(int x,int l,int r,int L,int R)
{
if(!x||l>R||r<L||L>R) return 0;
if(l>=L&&r<=R) return s[x].sum;
int mid=(l+r)>>1,re=0;
pushdown(x);
if(L<=mid) re+=query(lson,l,mid,L,R);
if(R>mid) re+=query(rson,mid+1,r,L,R);
return re;
}
void add(int x,int l,int r,int L,int R,int v)
{
if(!x||r<L||l>R||L>R) return;
if(l>=L&&r<=R) { mark(x,v); return; }
int mid=(l+r)>>1;
pushdown(x);
if(L<=mid) add(lson,l,mid,L,R,v);
if(R>mid) add(rson,mid+1,r,L,R,v);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
pushdown(x);
pushdown(y);
int now=newnode();
s[now].sum=s[x].sum+s[y].sum;
s[now].tag=s[x].tag+s[y].tag;
s[now].ls=merge(s[x].ls,s[y].ls);
s[now].rs=merge(s[x].rs,s[y].rs);
return now;
}
void dfs(int x,int l,int r)
{
if(l==r) { bu[l]+=s[x].tag; return; }
pushdown(x);
int mid=(l+r)>>1;
if(lson) dfs(lson,l,mid);
if(rson) dfs(rson,mid+1,r);
}
void clr()
{
int i,j;
for(i=1;i<=tot;++i) s[i].clr();
tot=0;
}
#undef lson
#undef rson
};
struct Solve
{
int tot,last;
vector<int>G[N<<1];
int pre[N<<1],mx[N<<1],ch[N<<1][26],rt[N<<1],tax[N<<1],rk[N<<1],id[N<<1];
void init() { last=tot=1; }
void extend(int c,int pos)
{
int np=++tot,p=last;
mx[np]=mx[p]+1,last=np;
for(;p&&!ch[p][c];p=pre[p]) ch[p][c]=np;
if(!p) pre[np]=1;
else
{
int q=ch[p][c];
if(mx[q]==mx[p]+1) pre[np]=q;
else
{
int nq=++tot;
mx[nq]=mx[p]+1;
pre[nq]=pre[q],pre[q]=pre[np]=nq;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;
}
}
seg::update(rt[np],1,n,pos,1);
G[np].push_back(pos);
}
void clr()
{
int i,j;
seg::clr();
for(i=1;i<=tot;++i)
{
G[i].clear();
rt[i]=mx[i]=pre[i]=tax[i]=id[i]=rk[i]=0;
memset(ch[i],0,sizeof(ch[i]));
}
tot=0;
}
void work()
{
int i,j;
init();
for(i=1;i<=n;++i) extend(S[i]-'a',i);
for(i=1;i<=tot;++i) ++tax[mx[i]];
for(i=1;i<=tot;++i) tax[i]+=tax[i-1];
for(i=1;i<=tot;++i) rk[tax[mx[i]]--]=i;
for(i=1;i<=tot;++i) id[i]=i;
for(i=tot;i>1;--i)
{
int u=rk[i];
int ff=pre[u];
int a=u,b=ff;
if(G[id[a]].size()>G[id[b]].size()) swap(a,b);
for(j=0;j<G[id[a]].size();++j)
{
int x=G[id[a]][j];
G[id[b]].push_back(x);
if(mx[ff]==0) continue;
bu[x]+=seg::query(rt[b],1,n,max(1,x-mx[ff]),x-1);
if(x<n)
{
seg::add(rt[b],1,n,x+1,min(n,x+mx[ff]),1);
}
}
id[ff]=id[b];
rt[ff]=seg::merge(rt[u],rt[ff]);
}
seg::dfs(rt[1],1,n);
clr();
}
}suf,pre;
void work()
{
int i,j;
scanf("%s",S+1),n=strlen(S+1);
pre.work();
for(i=1;i<=n;++i) A[i]=bu[i];
for(i=1;i<=n;++i) bu[i]=0;
for(i=1;n-i+1>i;++i) swap(S[i],S[n-i+1]);
suf.work();
for(i=1;i<=n;++i) B[i]=bu[i];
ll ans=0;
for(i=1;i<=n;++i) ans+=(ll)A[i]*B[n-i];
for(i=1;i<=n;++i) bu[i]=0;
printf("%lld
",ans);
}
int main()
{
int i,j,T;
// setIO("input");
scanf("%d",&T);
while(T--) work();
return 0;
}