円状に並べられた二進文字列 $a_0a_1a_2 \dots a_{n-1}$ が与えられる。毎秒、すべての $01$ を同時に $10$ に変更する。言い換えれば、$a_i = 0$ かつ $a_{(i+1) \pmod n} = 1$ である場合、$a_i$ と $a_{(i+1) \pmod n}$ を入れ替える。例えば、$100101110$ は $001010111$ に変化する。

無限秒の間に何種類の異なる文字列が現れるかを、$998244353$ を法として答えよ。

注記：二つの文字列 $a_0a_1 \dots a_{n-1}$ と $b_0b_1 \dots b_{n-1}$ は、ある整数 $i \in \{0, 1, \dots, n-1\}$ が存在して $a_i \neq b_i$ となる場合に異なるとみなす。したがって、文字列の巡回シフトは元の文字列とは異なる場合がある。

入力

最初の行にはテストケースの数 $T$ ($1 \le T \le 10^6$) が含まれる。

各テストケースについて、最初の行には二進文字列 $a_0a_1 \dots a_{n-1}$ ($a_i \in \{0, 1\}$) が含まれる。

すべてのテストケースにおける文字列の長さの総和は $10^7$ を超えないことが保証される。

出力

各テストケースについて、答えを表す整数を1行に出力せよ。

入出力例

入力 1

3
1
001001
0001111

出力 1

1
3
9