A dream. I am having a distant and long-lasting dream. I have been having this dream since a long time ago; In the dream, I gaze at the streets through the four seasons, Expecting to meet again with someone who will never arrive, Searching for something lost that I have long forgotten. How much time, how many years have flowed past me, In the endless dark night, I have always been waiting alone— — Waiting for the dawn that will surely come in the end. — Kanon

In the following, we define: String indices start from 1. For a string $s$, $s[l : r]$ denotes the string formed by concatenating $s_l, s_{l+1}, \dots, s_r$ in order. $a \oplus b$ denotes the bitwise XOR of $a$ and $b$ in binary. $\bigoplus_{i=1}^n a_i = a_1 \oplus a_2 \oplus \dots \oplus a_n$.

Ayu has a string $s$ of length $n$ consisting only of digits 0 and 1. She now needs to partition it into $k$ non-empty substrings $s[1 : p_1], s[p_1 + 1 : p_2], \dots, s[p_{k-1} + 1 : n]$, where $1 \le p_1 < p_2 < \dots < p_{k-1} < n$. For each substring, she decides to treat its leftmost character as the most significant bit and interpret it directly as a binary number. Formally, if she partitions a substring $s[l : r]$, it is treated as the decimal value $\sum_{i=l}^r (2^{r-i} \times s_i)$ represented in binary. There may be leading zeros.

Ayu defines the weight of a partition scheme as the bitwise XOR sum of these binary numbers. She wants to know the maximum possible weight among all partition schemes, and the number of partition schemes that achieve this maximum weight. However, Ayu has forgotten the value of $k$, so she needs to find the corresponding answers for all $k = 1, 2, \dots, n$. But she is a child who cannot even easily solve cubic equations, so she has come to ask for your help.

Input

Each test case contains multiple test data. The first line contains an integer $T (1 \le T \le 10^4)$, representing the number of test cases. For each test case, a single line containing a string $s$ consisting only of 0s and 1s is given. It is guaranteed that the sum of the lengths of the strings in all test data within each test point does not exceed $3 \times 10^6$.

Output

For each test case, to avoid massive output, use the following output method (the correct solution to this problem does not depend on this output method): Let $p_1, p_2, \dots, p_n$ be the maximum values for $k = 1, 2, \dots, n$ modulo 998244353, and $q_1, q_2, \dots, q_n$ be the number of partition schemes with the maximum weight modulo 998244353. Output four integers $A, B, C, D$ on a single line, separated by spaces. The values of $A, B, C, D$ are:

$$A = \bigoplus_{i=1}^n p_i$$ $$B = \bigoplus_{i=1}^n q_i$$ $$C = \bigoplus_{i=1}^n (p_i \times i)$$ $$D = \bigoplus_{i=1}^n (q_i \times i)$$

Note that only the final maximum values and the number of partition schemes achieving the maximum weight need to be taken modulo 998244353. You do not need to take the modulo during the calculation of $A, B, C, D$.

Examples

Input 1

5
110
11010
1011010
101111011
11010101101

Output 1

5 2 0 6
19 3 24 9
101 4 109 30
405 7 382 33
1225 6 1144 53

Note

For the first test case of the example, the answers for $k = 1, 2, 3$ are calculated as follows:

• $k = 1$: The maximum value is itself $(110)_2 = 6$, and the number of schemes is 1.
• $k = 2$: When the partition scheme is $(11, 0)$ or $(1, 10)$, the maximum value can be obtained, which is $(11)_2 \oplus (0)_2 = (1)_2 \oplus (10)_2 = 3$, and the number of schemes is 2.
• $k = 3$: The only partition scheme is $(1, 1, 0)$, the maximum value is $(1)_2 \oplus (1)_2 \oplus (0)_2 = 0$, and the number of schemes is 1.

Thus, we get $p = \{6, 3, 0\}, q = \{1, 2, 1\}$, and we can calculate $A, B, C, D$ respectively:

$$A = 6 \oplus 3 \oplus 0 = 5$$ $$B = 1 \oplus 2 \oplus 1 = 2$$ $$C = (6 \times 1) \oplus (3 \times 2) \oplus (0 \times 3) = 0$$ $$D = (1 \times 1) \oplus (2 \times 2) \oplus (1 \times 3) = 6$$

Therefore, the output numbers are 5, 2, 0, 6.