H. 凯文与奇怪操作

单次测试时间限制：$2$ 秒 内存限制：$256$ 兆字节

凯文正在唐人街研究与二进制字符串相关的问题。正当他毫无头绪时，一位陌生人走了过来，向他介绍了一种奇特的操作：

假设当前二进制字符串为 $t$，长度为 $|t|$。选择一个整数 $1 \le p \le |t|$。对所有满足 $1 \le i < p$ 的位置，同时执行操作 $t_i = \max(t_i, t_{i+1})$，随后删除位置 $p$ 上的字符。

举个例子，假设当前二进制字符串是 $01001$，选择 $p=4$。对 $t_1$、$t_2$、$t_3$ 执行 $t_i = \max(t_i, t_{i+1})$ 操作，字符串变为 $11001$，随后删除 $t_4$，最终得到 $1101$。

凯文觉得这个奇怪的操作非常有趣。因此他想问问你：给定一个二进制字符串 $s$，通过任意次数（可以是 $0$ 次）该操作，你能得到多少种不同的非空二进制字符串？

由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

输入格式

每个测试包含多组数据。 第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

对于每个测试用例，仅有一行输入一个二进制字符串 $s$（$1 \le |s| \le 10^6$）。

保证所有测试用例的字符串长度之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例输入

2
11001
000110111001100

样例输出

9
73

样例说明

在第一个测试用例中，你能得到的所有不同字符串为： $11001$、$1001$、$1101$、$001$、$101$、$111$、$01$、$11$、$1$，总计 $9$ 种。