3917.T3-[NOIP2020] 字符串匹配(match)

小 $ C $ 学习完了字符串匹配的相关内容，现在他正在做一道习题。

对于一个字符串 $ S $ ，题目要求他找到 $ S $ 的所有具有下列形式的拆分方案数：

$ S=ABC $ ， $ S=ABABC $ ， $ S=ABAB⋯ABC $ ，其中 $ A，B，C $ 均是非空字符串，且 $ A $ 中出现奇数次的字符数量不超过 $ C $ 中出现奇数次的字符数量。

更具体地，我们可以定义 $ AB $ 表示两个字符串 $ A，B $ 相连接，例如 $ A=aab $ ， $ B=ab $ ，则 $ AB=aabab $ 。

并递归地定义 $ A^1=A，A^n=A^{n−1}A $ （ $ n≥2 $ 且为正整数），例如 $ A=abb $ ，则 $ A^3=abbabbabb $ 。

则小 $ C $ 的习题是求 $ S=(AB)^iC $ 的方案数，其中 $ F(A)≤F(C)，F(S) $ 表示字符串 $ S $ 中出现奇数次的字符的数量。

两种方案不同当且仅当拆分出的 $ A、B、C $ 中有至少一个字符串不同。

小 $ C $ 并不会做这道题，只好向你求助，请你帮帮他。

#### 输入格式

本题有多组数据，输入文件第一行一个正整数 $ T $ 表示数据组数。

每组数据仅一行一个字符串 $ S $ ，意义见题目描述。 $ S $ 仅由英文小写字母构成。

#### 输出格式

对于每组数据输出一行一个整数表示答案。

#### 数据范围

| 测试点编号 | |$S$|≤ | 特殊性质 |
| --- | --- | --- |
| $1∼4$ | $10$ | 无 |
| $5∼8$ | $100$ | 无 |
| $9∼12$ | $1000$ | 无 |
| $13∼14$ | $2^{15}$ | $S$ 中只包含一种字符 |
| $15∼17$ | $2^{16}$ | $S$ 中只包含两种字符 |
| $18∼21$ | $2^{17}$ | 无 |
| $22∼25$ | $2^{20}$ | 无 |

对于所有测试点，保证 $ 1≤T≤5 $ ， $ 1≤|S|≤2^{20} $ 。

#### 输入样例$1$：

```
3
nnrnnr
zzzaab
mmlmmlo

```
#### 输出样例$1$：

```
8
9
16

```
#### 样例$1$解释

对于第一组数据，所有的方案为

1. $A=n$，$B=nr$，$C=nnr$。

2. $A=n$，$B=nrn$，$C=nr$。

3. $A=n$，$B=nrnn$，$C=r$。

4. $A=nn$，$B=r$，$C=nnr$。

5. $A=nn$，$B=rn$，$C=nr$。

6. $A=nn$，$B=rnn$，$C=r$。

7. $A=nnr$，$B=n$，$C=nr$。

8. $A=nnr$，$B=nn$，$C=r$。

#### 输入样例$2$：

```
5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

```
#### 输出样例$2$：

```
156
138
138
147
194

```