Vous disposez d'une chaîne binaire $a_0a_1a_2 \dots a_{n-1}$ disposée sur un cycle. Chaque seconde, vous changez simultanément chaque $01$ en $10$. En d'autres termes, si $a_i = 0$ et $a_{(i+1) \bmod n} = 1$, vous échangez $a_i$ et $a_{(i+1) \bmod n}$. Par exemple, nous transformerons $100101110$ en $001010111$.

Vous devez répondre au nombre de chaînes différentes qui apparaîtront au cours d'un temps infini, modulo $998244353$.

Remarque : Deux chaînes $a_0a_1 \dots a_{n-1}$ et $b_0b_1 \dots b_{n-1}$ sont différentes s'il existe un entier $i \in \{0, 1, \dots, n-1\}$ tel que $a_i \neq b_i$. Ainsi, les décalages cycliques d'une chaîne peuvent être différents de la chaîne originale.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^6$) – le nombre de cas de test.

Pour chaque cas de test, la première ligne contient une chaîne binaire $a_0a_1 \dots a_{n-1}$ ($a_i \in \{0, 1\}$).

Il est garanti que la somme des longueurs des chaînes sur tous les cas de test n'excède pas $10^7$.

Sortie

Pour chaque cas de test, affichez un entier représentant la réponse sur une ligne.

Exemples

Entrée 1

3
1
001001
0001111

Sortie 1

1
3
9