{"raw_statement":[{"iden":"statement","content":"You are given a binary string $a_0a_1a_2\\dots a_{n-1}$ arranged on a cycle. Each second, you will change every $01$ to $10$ simultaneously. In other words, if $a_i = 0$ and $a_{(i+1) \\bmod n} = 1$, you swap $a_i$ and $a_{(i+1)\\bmod n}$. For example, we will change $\\texttt{100101110}$ to $\\texttt{001010111}$.\n\nYou need to answer how many different strings will occur in infinite seconds, modulo $998244353$.\n\nNote: Two strings $a_0a_1\\dots a_{n-1}$ and $b_0b_1\\dots b_{n-1}$ are different if there exists an integer $i\\in \\{0,1,\\ldots, n-1\\}$ such that $a_i\\neq b_i$. Thus, the cyclic shifts of a string may be different from the original string."},{"iden":"input","content":"The first line contains an integer $T$ $(1\\leq T\\leq 10^6)$ $-$ the number of test cases.\n\nFor each test case, the first line contains a binary string $a_0 a_1 \\dots a_{n-1}$ $(a_i \\in \\{0, 1\\})$.\n\nIt is guaranteed that the sum of lengths of strings over all test cases does not exceed $10^7$."},{"iden":"output","content":"For each test case, output one integer representing the answer in one line."}],"translated_statement":null,"sample_group":[["3\n1\n001001\n0001111","1\n3\n9"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}