Description

给定一个排列在环上的二进制字符串 $a_0a_1a_2\dots a_{n-1}$。每一秒钟，你会同时将每个 $01$ 变为 $10$。换句话说，如果 $a_i = 0$ 且 $a_{(i+1) \bmod n} = 1$，则交换 $a_i$ 和 $a_{(i+1)\bmod n}$。例如，我们将 $\texttt{100101110}$ 变为 $\texttt{001010111}$。

你需要回答在无限秒内会出现多少种不同的字符串，取模 $998244353$。

注意：如果存在整数 $i\in \{0,1,\ldots, n-1\}$ 使得 $a_i\neq b_i$，则两个字符串 $a_0a_1\dots a_{n-1}$ 和 $b_0b_1\dots b_{n-1}$ 是不同的。因此，字符串的循环移位可能与原始字符串不同。

Input Format

第一行包含一个整数 $T$ $(1\leq T\leq 10^6)$ $-$ 测试用例的数量。

对于每个测试用例，第一行包含一个二进制字符串 $a_0 a_1 \dots a_{n-1}$ $(a_i \in \{0, 1\})$。

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

Output Format

对于每个测试用例，输出一行一个整数，表示答案。

翻译来自于：ChatGPT

3
1
001001
0001111

1
3
9