#804. 字符串匹配

字符串匹配

题目描述

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

对于一个字符串 SS,题目要求他找到 SS 的所有具有下列形式的拆分方案数: S=ABCS = ABCS=ABABCS = ABABCS=ABABABCS = ABAB\cdots ABC,其中 AABBCC 均是非空字符串,且 AA 中出现奇数次的字符数量不超过 CC 中出现奇数次的字符数量。

更具体地,我们可以定义 ABAB 表示两个字符串 A,BA, B 相连接,例如 A=aabA = \text{aab}B=abB = \text{ab},则 AB=aababAB = \text{aabab}

并递归地定义 A1=AA^1 = AAn=An1AA^n = A^{n-1}An2n\ge2 且为正整数)。例如 A=abbA = \text{abb},则 A3=abbabbabbA^3 = \text{abbabbabb}

则小 C 的习题是求 S=(AB)iCS = (AB)^iC 的方案数,其中 F(A)F(C)F(A)\le F(C)F(S)F(S ) 表示字符串 SS 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 AABBCC 中有至少一个字符串不同。

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

输入格式

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

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

输出格式

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

样例

样例 1

输入数据:

3
nnrnnr
zzzaab
mmlmmlo

输出数据:

8
9
16

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

  1. A=nA=\color{blue}{\texttt{n}}B=nrB=\color{blue}{\texttt{nr}}C=nnrC=\color{blue}{\texttt{nnr}}
  2. A=nA=\color{blue}{\texttt{n}}B=nrnB=\color{blue}{\texttt{nrn}}C=nrC=\color{blue}{\texttt{nr}}
  3. A=nA=\color{blue}{\texttt{n}}B=nrnnB=\color{blue}{\texttt{nrnn}}C=rC=\color{blue}{\texttt{r}}
  4. A=nnA=\color{blue}{\texttt{nn}}B=rB=\color{blue}{\texttt{r}}C=nnrC=\color{blue}{\texttt{nnr}}
  5. A=nnA=\color{blue}{\texttt{nn}}B=rnB=\color{blue}{\texttt{rn}}C=nrC=\color{blue}{\texttt{nr}}
  6. A=nnA=\color{blue}{\texttt{nn}}B=rnnB=\color{blue}{\texttt{rnn}}C=rC=\color{blue}{\texttt{r}}
  7. A=nnrA=\color{blue}{\texttt{nnr}}B=nB=\color{blue}{\texttt{n}}C=nrC=\color{blue}{\texttt{nr}}
  8. A=nnrA=\color{blue}{\texttt{nnr}}B=nnB=\color{blue}{\texttt{nn}}C=rC=\color{blue}{\texttt{r}}

样例 2

输入数据:

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

输出数据:

156
138
138
147
194

数据范围与提示

测试点编号 S\vert S\vert \le 特殊限制
141\sim 4 1010
585\sim 8 100100
9129\sim 12 10001000
131413\sim 14 2152^{15} SS 中只包含一种字符
151715\sim 17 2162^{16} SS 中只包含两种字符
182118\sim 21 2172^{17}
222522\sim 25 2202^{20}

对于所有测试点,保证 1T51\le T\le51S2201\le |S|\le 2^{20}