# [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

### 样例输入 #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$ |                    |