Вам дана бинарная строка $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

3
1
001001
0001111

Выходные данные 1

1
3
9