給你一個排列在環上的二進位字串 $a_0a_1a_2 \dots a_{n-1}$。每一秒，你會同時將所有的 $01$ 變為 $10$。換句話說，如果 $a_i = 0$ 且 $a_{(i+1) \bmod n} = 1$，則交換 $a_i$ 與 $a_{(i+1) \bmod n}$。例如，我們會將 $100101110$ 變為 $001010111$。

你需要回答在無限的時間內會出現多少種不同的字串，答案對 $998244353$ 取模。

注意：若存在一個整數 $i \in \{0, 1, \dots, n-1\}$ 使得 $a_i \neq b_i$，則稱兩個字串 $a_0a_1 \dots a_{n-1}$ 與 $b_0b_1 \dots b_{n-1}$ 不同。因此，字串的循環移位可能與原始字串不同。

輸入格式

第一行包含一個整數 $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