#9007. 「第7次PTA认证」成双成对 普及+/提高

如果一个字符串可以被拆分为 的形式，其中 和 是任意非空字符串，则我们称该字符串的这种拆分是“成双成对”的。例如，对于字符串

，如果令 ，，我们就找到了这个字符拆分成 的一种方式。一个字符串可能没有“成双成对”，也可能存在不止一种“成双成对”。

比如我们令 ，也可以用 表示出上述字符串；但是，字符串 就没有“成双成对”。现在给出一个长度为 的字符串 ，我

们需要求出，在它所有子串的所有拆分方式中，“成双成对”的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

1、出现在不同位置的相同子串，我们认为是不同的子串，它们的“成双成对”均会被记入答案。

2、在一个拆分中，允许出现 。例如 存在拆分 。

3、字符串本身也是它的一个子串。

每个输入文件包含多组数据。

输入文件的第一行只有一个整数 ，表示数据的组数。

接下来 行，每行包含一个仅由英文小写字母构成的字符串 ，意义如题所述。

输出 行，每行包含一个整数，表示字符串 所有子串的所有拆分中，总共有多少个是“成双成对”。

样例输入

4 
aabbbb 
cccccc 
aabaabaabaa 
bbaabaababaaba

样例输出

3
5 
4 
7

样例解释

我们用 S[i,j]表示字符串 S 第 i 个字符到第 j 个字符的子串（从 1 开始计数）。第一组数据中，共有三个子串存在“成双成对”：

S[1,4]=aabb，“成双成对”为 A=a，B=b； S[3,6]=bbbb，“成双成对”为 A=b，B=b； S[1,6]=aabbbb，“成双成对”为 A=a，B=bb。

而剩下的子串不存在“成双成对”，所以第一组数据的答案是 3。

第二组数据中，有两类，总共四个子串存在“成双成对”：

对于子串 S[1,4]=S[2,5]=S[3,6]=cccc，它们的“成双成对”相同，均为 A=c，B=c，但由于这些子串位置不同，因此要计算三次；

对于子串 S[1,6]=cccccc，它的“成双成对”有两种：A=c，B=cc 和 A=cc，B=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。

对于全部的测试点，保证 。以下对数据的限制均是对于单组输入数据而言的，也就是说同一个测试点下的 组数据均满足限制条件。

我们假定 为字符串 的长度，每个测试点的详细数据范围见下表：