问题 F: 字符串匹配

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

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

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

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

并递归地定义 A¹=A，Aⁿ=Aⁿ⁻¹ A（n≥2 且为正整数）。例如 A=abb，则A³=abbabbabb。

则小 C 的习题是求 S=(AB)ⁱC 的方案数，其中 F(A)≤F(C，F(S) 表示字符串 S中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 A、B、C 中有至少一个字符串不同。

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

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

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

【样例 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
ggggggggggggggbaab

156
138
138
147
194