4603 - NOIP 2020 提高 第二题 字符串匹配（string）
Time Limit : 1 秒
Memory Limit : 512 MB
小 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 ^− ^1A（n ≥ 2 且为正整数）。例如 A = abb，则 A^3 = abbabbabb。 则小 C 的习题是求 S = (AB)^iC 的方案数，其中 F(A) ≤ F(C)，F(S ) 表示字符串 S 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 A、B、C 中有至少一个 字符串不同。 小 C 并不会做这道题，只好向你求助，请你帮帮他
Input
本题有多组数据，输入文件第一行一个正整数 T 表示数据组数。 每组数据仅一行一个字符串 S，意义见题目描述。S 仅由英文小写字母构成。
Output
对于每组数据输出一行一个整数表示答案。
Examples
Input
3 nnrnnr zzzaab mmlmmlo
Output
8 9 16
Input
5 kkkkkkkkkkkkkkkkkkkk lllllllllllllrrlllrr cccccccccccccxcxxxcc ccccccccccccccaababa ggggggggggggggbaabab
Output
156 138 138 147 194
Input
5 rrrrrrrrrr iiiiiiiwzr dididididi wwwwzqcjvv mbymbyhgpc
Output
30 39 30 28 33 yang
Hint
【样例 1 解释】 对于第一组数据，所有的方案为：
- A=n，B=nr，C=nnr。
- A=n，B=nrn，C=nr。
- A=n，B=nrnn，C=r。
- A=nn，B=r，C=nnr。
- A=nn，B=rn，C=nr。
- A=nn，B=rnn，C=r。
- A=nnr，B=n，C=nr。
- A=nnr，B=nn，C=r。
样例4输入 5 cccccccccc lllllllket tututututu ccbuxccbux pnppnpnlwl
样例4输出 30 39 30 26 32
