1001. runs

题目描述

你知道吗，中文里拼音为 "run" 的常用字只有 "润"，"闰" 字多数人只有在鲁迅的文章里以名字的方式见到过。

没了。

定义一个字符串是重串，当前仅当它可以被表示为 $u^{k}(k\geq 2)$ 的形式，即将字符串 $u$ 连续拼接 $k$ 次。

定义一个字符串 $s$ 的划分为一个集合 $\{l_k, r_k\}$，满足 $l_1=1, r_{k}=|s|, l_{i}=r_{i-1}+1, l_{i}\leq r_{i}$, $s=s[l_1, r_1]+s[l_2, r_2]+\cdots+s[l_{k}, r_{k}]$。

定义一个字符串 $s$ 的一个划分 $\{l_k, r_k\}$ 是好的，当且仅当 $\forall i, s[l_i, r_{i}]$ 不是重串。

给出一个 01 串，求它的好的划分的数量，对 998244353 取模。

输入格式

第一行一个整数 $T$（$T\leq 100$），表示数据组数。

接下来 $T$ 行，每行一个 01 串，表示询问的字符串 $s（|s|\leq 10^{6}, \sum |s|\leq 9\times 10^{6}，s[i]\in \{0, 1\}）$。

输出格式

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

样例输入

5
1
01
001
000100011
1010101010

样例输出

1
2
3
71
345

来源：2026杭电多校-测试专用（四川大学） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1231&pid=1001