B-[NOIP2020]字符串匹配（string）_NOIP2020提高组复赛（官方数据）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小 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¹ = A，Aⁿ = A^n-1A（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

输入

复制

3
nnrnnr
zzzaab
mmlmmlo

输出

复制

8
9
16

说明

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
ggggggggggggggbaabab

输出

复制

备注:

                         
对于所有测试点，保证 1 ≤ T ≤ 5，1 ≤ |S| ≤ 2²⁰。