#2303. 「NOIP2020」字符串匹配 暂未评定

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

对于一个字符串 ，题目要求他找到 的所有具有下列形式的拆分方案数： ，，，其中 ，， 均是非空字符串，且 中出现奇数次的字符数量不超过 中出现奇数次的字符数量。

更具体地，我们可以定义 表示两个字符串 相连接，例如 ，，则 。

并递归地定义 ，（ 且为正整数）。例如 ，则 。

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

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

从文件 string.in 中读入数据。

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

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

输出到文件 string.out 中。

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

样例1

输入样例

3
nnrnnr
zzzaab
mmlmmlo

输出样例

8
9
16

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

1. ，，。
2. ，，。
3. ，，。
4. ，，。
5. ，，。
6. ，，。
7. ，，。
8. ，，。

样例2

样例输入

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

样例输出

156
138
138
147
194

样例3

见附加文件中的 与 。

样例4

见附加文件中的 与 。

对于所有测试点，保证 ，。