题目描述

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

例如，对于字符串 aabaabaa，如果令 A=aab，B=a，我们就找到了这个字符 串拆分成 AABB 的一种方式。

一个字符串可能没有“成双成对”，也可能存在不止一种“成双成对”。

比如我们令 A=a，B=baa，也可以用 AABB 表示出上述字符串；但是，字符串 abaabaa 就没有“成双成对”。

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

以下事项需要注意：

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

2、在一个拆分中，允许出现 A=B。例如 cccc 存在拆分 A=B=c。

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

输入格式

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

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

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

输出格式

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

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。

数据范围

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

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

测试点编号	n 的范围	特殊性质
1∼2	n≤300	S 中所有字符相同
3∼6	n≤30	无
7∼8	n≤100
9∼10	n≤2000