Dany jest ciąg binarny $a_0a_1a_2 \dots a_{n-1}$ ułożony w cykl. W każdej sekundzie jednocześnie zmieniasz każde wystąpienie $01$ na $10$. Innymi słowy, jeśli $a_i = 0$ oraz $a_{(i+1) \pmod n} = 1$, zamieniasz miejscami $a_i$ oraz $a_{(i+1) \pmod n}$. Na przykład, ciąg $100101110$ zmieni się w $001010111$.

Musisz odpowiedzieć na pytanie, ile różnych ciągów pojawi się w nieskończonym czasie, modulo $998244353$.

Uwaga: Dwa ciągi $a_0a_1 \dots a_{n-1}$ oraz $b_0b_1 \dots b_{n-1}$ są różne, jeśli istnieje taka liczba całkowita $i \in \{0, 1, \dots, n-1\}$, że $a_i \neq b_i$. Zatem przesunięcia cykliczne ciągu mogą być różne od ciągu oryginalnego.

Wejście

Pierwsza linia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^6$) – liczbę zestawów danych.

Dla każdego zestawu danych, pierwsza linia zawiera ciąg binarny $a_0a_1 \dots a_{n-1}$ ($a_i \in \{0, 1\}$).

Gwarantuje się, że suma długości ciągów we wszystkich zestawach danych nie przekracza $10^7$.

Wyjście

Dla każdego zestawu danych wyprowadź w jednej linii jedną liczbę całkowitą reprezentującą wynik.

Przykład

Wejście 1

3
1
001001
0001111

Wyjście 1

1
3
9