[NOI2016]优秀的拆分

题目描述

如果一个字符串可以被拆分为 $\text{AABB}$ 的形式,其中 $\text{A}$ 和 $\text{B}$ 是任意**非空**字符串,则我们称该字符串的这种拆分是优秀的。 例如,对于字符串 $ \texttt{aabaabaa} $ ,如果令 $\text{A}=\texttt{aab}$,$\text{B}=\texttt{a}$,我们就找到了这个字符串拆分成 $\text{AABB}$ 的一种方式。 一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。 比如我们令 $\text{A}=\texttt{a}$,$\text{B}=\texttt{baa}$,也可以用 $\text{AABB}$ 表示出上述字符串;但是,字符串 $\texttt{abaabaa}$ 就没有优秀的拆分。 现在给出一个长度为 $n$ 的字符串 $S$,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。 以下事项需要注意: 1. 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。 2. 在一个拆分中,允许出现 $\text{A}=\text{B}$。例如 $\texttt{cccc}$ 存在拆分 $\text{A}=\text{B}=\texttt{c}$。 3. 字符串本身也是它的一个子串。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

输出样例 #1

3
5
4
7

说明

### 样例解释 我们用 $S[i, j]$ 表示字符串 $S$ 第 $i$ 个字符到第 $j$ 个字符的子串(从 $1$ 开始计数)。 第一组数据中,共有三个子串存在优秀的拆分: $S[1,4]=\texttt{aabb}$,优秀的拆分为 $\text{A}=\texttt{a}$,$\text{B}=\texttt{b}$; $S[3,6]=\texttt{bbbb}$,优秀的拆分为 $\text{A}=\texttt{b}$,$\text{B}=\texttt{b}$; $S[1,6]=\texttt{aabbbb}$,优秀的拆分为 $\text{A}=\texttt{a}$,$\text{B}=\texttt{bb}$。 而剩下的子串不存在优秀的拆分,所以第一组数据的答案是 $3$。 第二组数据中,有两类,总共四个子串存在优秀的拆分: 对于子串 $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$,它们优秀的拆分相同,均为 $\text{A}=\texttt{c}$,$\text{B}=\texttt{c}$,但由于这些子串位置不同,因此要计算三次; 对于子串 $S[1,6]=\texttt{cccccc}$,它优秀的拆分有两种:$\text{A}=\texttt{c}$,$\text{B}=\texttt{cc}$ 和 $\text{A}=\texttt{cc}$,$\text{B}=\texttt{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 \leq T \leq 10$。以下对数据的限制均是对于单组输入数据而言的,也就是说同一个测试点下的 $T$ 组数据均满足限制条件。 我们假定 $n$ 为字符串 $S$ 的长度,每个测试点的详细数据范围见下表: | 测试点编号 | $n \leq$ | 特殊性质 | | ------------ | --------- | ------------------ | | $1 \sim 2$ | $300$ | $S$ 中所有字符相同 | | $3 \sim 4$ | $2\,000$ | $S$ 中所有字符相同 | | $5 \sim 6$ | $10$ | | | $7 \sim 8$ | $20$ | | | $9 \sim 10$ | $30$ | | | $11 \sim 12$ | $50$ | | | $13 \sim 14$ | $100$ | | | $15$ | $200$ | | | $16$ | $300$ | | | $17$ | $500$ | | | $18$ | $1\,000$ | | | $19$ | $2\,000$ | | | $20$ | $30\,000$ | |