1283: #2083. 「NOI2016」优秀的拆分

每个输入文件包含多组数据。
输入文件的第一行只有一个整数 $T$，表示数据的组数。
接下来 $T$ 行，每行包含一个仅由英文小写字母构成的字符串 $S$，意义如题所述。

输出 $T$ 行，每行包含一个整数，表示字符串 $S$ 所有子串的所有拆分中，总共有多少个是优秀的拆分。

样例输入

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

样例输出

3
5
4
7

样例解释

我们用 $S[i,j]$ 表示字符串 $S$ 第 $i$ 个字符到第 $j$ 个字符的子串（从 $1$ 开始计数）。

第一组数据中，共有三个子串存在优秀的拆分：
$S[1,4]=\text{aabb}$，优秀的拆分为 $\text{A}=\text{a}$，$\text{B}=\text{b}$；
$S[3,6]=\text{bbbb}$，优秀的拆分为 $\text{A}=\text{b}$，$\text{B}=\text{b}$；
$S[1,6]=\text{aabbbb}$，优秀的拆分为 $\text{A}=\text{a}$，$\text{B}=\text{bb}$。
而剩下的子串不存在优秀的拆分，所以第一组数据的答案是 $3$。

第二组数据中，有两类，总共四个子串存在优秀的拆分：
对于子串 $S[1,4]=S[2,5]=S[3,6]=\text{cccc}$，它们优秀的拆分相同，均为 $\text{A}=\text{c}$，$\text{B}=\text{c}$，但由于这些子串位置不同，因此要计算三次；
对于子串 $S[1,6]=\text{cccccc}$，它优秀的拆分有两种：$\text{A}=\text{c}$，$\text{B}=\text{cc}$ 和 $\text{A}=\text{cc}$，$\text{B}=\text{c}$，它们是相同子串的不同拆分，也都要计入答案。
所以第二组数据的答案是 $3+2=5$。

第三组数据中，$S[1,8]$ 和 $S[4,11]$ 各有两种优秀的拆分，其中 $S[1,8]$ 是问题描述中的例子，所以答案是 $2+2=4$。

第四组数据中，$S[1,4]$，$S[6,11]$，$S[7,12]$，$S[2,11]$，$S[1,8]$ 各有一种优秀的拆分，$S[3,14]$ 有两种优秀的拆分，所以答案是 $5+2=7$。

对于全部的测试点，$1\le T\le 10,n\le 30000$。