给定一个排列在环上的二进制字符串 $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$ 取模。

注意：两个字符串 $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