Background

Easy Counting Problem

身のうさを思ひしらでややみなまし そむくならひのなき世なりせば

Problem Description

Given a binary string $S$ of length $N$, you can perform some operations. In each operation, choose a substring of length $3$ and replace it with its median (note that it becomes a single digit). Ask how many different strings can be obtained.

Output the answer modulo $998244353$.

Input Format

This problem has multiple test cases. The first line contains the number of test cases $T$.

For each test case, input only one string $S$, representing the given binary string.

Output Format

For each test case, output one integer per line, which is the answer modulo $998244353$.

4
1001
111000
101010
111000101010

3
7
3
25

Hint

Sample Explanation

It can be proven that $1001$ can only obtain the strings $10$, $01$, and $1001$ through the operations, so the answer for the first test case in the sample is $3$.

Constraints

For $100\%$ of the testdata, $1 \le N \le 5\times {10}^6$, $S_i \in \{0,1\}$, and $1 \le T \le 5$.

Special Property A: It is guaranteed that $S_i = 0$.

Special Property B: It is guaranteed that $S_{2k} = 0$ and $S_{2k+1} = 1$.

String indices start from $1$.

Translated by ChatGPT 5