时间限制：1秒　　内存限制：256M

---

【问题描述】

　　小 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−1}A\)（\(n ≥ 2\) 且为正整数）。例如 \(A\) = abb，则 \(A^3\) = abbabbabb。
　　则小 C 的习题是求 \(S = (AB)^iC\) 的方案数，其中 \(F(A) ≤ F(C)\)，\(F(S)\) 表示字符串 \(S\) 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 \(A、B、C\) 中有至少一个字符串不同。
　　小 C 并不会做这道题，只好向你求助，请你帮帮他。

【输入格式】

　　本题有多组数据，输入文件第一行一个正整数 \(T\) 表示数据组数。
　　每组数据仅一行一个字符串 \(S\)，意义见题目描述。\(S\) 仅由英文小写字母构成。

【输出格式】

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

【输入输出样例1】

　Input

3
nnrnnr
zzzaab
mmlmmlo

　Output

8
9
16

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

　Input

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

　Output

156
138
138
147
194

【数据说明】

　　对于所有测试点，保证 \(1 ≤ T ≤ 5\)，\(1 ≤ |S | ≤ 2^20\)。

【来源】

　　Mr.he