CF2048H.Kevin and Strange Operation

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

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

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

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

由于答案可能非常大，你只需要输出结果对 $998\,244\,353$ 取模后的值。

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

对于每个测试用例，只有一行，包含一个二进制字符串 $s$（$1 \leq |s| \leq 10^6$）。

保证所有测试用例中 $|s|$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示可以通过任意次数操作得到的不同非空二进制字符串的数量，对 $998\,244\,353$ 取模。

在第一个测试用例中，所有可以得到的二进制字符串为：11001、1001、1101、001、101、111、01、11 和 1。一共有 $9$ 个。

由 ChatGPT 4.1 翻译