65017 - [NOIP2020] 字符串匹配 string

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

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

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

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

并递归地定义 A^1=A，A^n = A^{n - 1} A（n \ge 2 且为正整数）。例如 A = \texttt{abb}，则 A^3=\texttt{abbabbabb}。

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

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

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

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

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

【样例 #1 解释】

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

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

【数据范围】

对于所有测试点，保证 1 \le T \le 5，1 \le |S| \le 2^{20}。