OIer博客

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

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

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

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

并递归地定义 A1=A，An=An−1A（$n\ge 2$ 且为正整数）。例如 $A=\text{abb}$，则 A3=abbabbabb。

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

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

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

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

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

【样例 #1 解释】

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

1. $A=\text{n}$，$B=\text{nr}$，$C=\text{nnr}$。
2. $A=\text{n}$，$B=\text{nrn}$，$C=\text{nr}$。
3. $A=\text{n}$，$B=\text{nrnn}$，$C=\text{r}$。
4. $A=\text{nn}$，$B=\text{r}$，$C=\text{nnr}$。
5. $A=\text{nn}$，$B=\text{rn}$，$C=\text{nr}$。
6. $A=\text{nn}$，$B=\text{rnn}$，$C=\text{r}$。
7. $A=\text{nnr}$，$B=\text{n}$，$C=\text{nr}$。
8. $A=\text{nnr}$，$B=\text{nn}$，$C=\text{r}$。

【数据范围】

对于所有测试点，保证 $1\le T\le 5$，1≤∣S∣≤220。