题目背景

梦。

我做着一个悠远而长久的梦。

从很久以前就一直在做着这个梦；

在梦中我凝望四季的街道，

期望与永远不会到来的人再度见面，

找寻连自己也早已忘却的遗失的东西。

多少时间、多少岁月从我身边流逝而过，

在无尽的黑夜中，一直、一直都在孤单地等待着——

等待着最后那必将到来的黎明。

——《Kanon》

题目描述

下文中，我们约定：

• 字符串的下标从 $1$ 开始。
• 对于一个字符串 $s$，$s[l:r]$ 表示将 $s_l,s_{l+1},\cdots,s_r$ 依次连接形成的字符串。
• $a\oplus b$ 表示 $a$ 和 $b$ 在二进制下按位异或得到的值。
• $\bigoplus\limits_{i=1}^na_i=a_1\oplus a_2\oplus\cdots\oplus a_n$。

---

亚由的梦里有一个长度为 $n$ 的、仅由数字 $0$ 和 $1$ 构成的字符串 $s$。她现在需要将其划分成 $k$ 个非空子段 $s[1:p_1],s[p_1+1:p_2],\cdots,s[p_{k-1}+1:n]$，其中 $1\le p_1<p_2<\cdots<p_{k-1}<n$。

对于每个子段，她决定将其最左侧视为二进制的最高位，直接看成二进制数。形式化地，如果她划分出一个子段 $s[l:r]$，则将这个子段看作十进制数 $\sum\limits_{i=l}^r(2^{r-i}\times s_i)$ 在二进制下的表示。可能有前导零。

现在亚由定义一种划分方案的权值为，这些二进制数的按位异或和。她现在想知道所有划分方案中权值最大是多少，以及权值恰好为最大值的划分方案数量。

然而亚由忘记了 $k$ 的值，因此她需要对 $k=1,2,\cdots,n$ 都求出对应的答案。

可她是个连三次方程都不能轻松解出的小朋友，于是她来求助祐一——也就是您了。

输入格式

每个测试点包含多组测试数据。第一行给定一个整数 $T(1\leq T\leq 10^4)$，表示测试数据组数。

对于每组测试数据，给定一行一个仅由 $0$ 和 $1$ 构成的字符串 $s$。

保证在每个测试点中所有测试数据的字符串的长度的总和不超过 $3\times 10^6$。

输出格式

对于每组数据，为了避免大量的输出，采用如下输出方式（本题正解不依赖该输出方式）：

设对于 $k=1,2,\cdots,n$，对应的最大值对 $998244353$ 取模后，为 $p_1,p_2,\cdots,p_n$；权值为最大值的划分方案数对 $998244353$ 取模后，为 $q_1,q_2,\cdots,q_n$。则一行输出四个整数 $A,B,C,D$，用半角空格隔开。其中 $A,B,C,D$ 的值分别为：

$$\begin{aligned} A&=\bigoplus_{i=1}^np_i\\ B&=\bigoplus_{i=1}^nq_i\\ C&=\bigoplus_{i=1}^n(p_i\times i)\\ D&=\bigoplus_{i=1}^n(q_i\times i)\\ \end{aligned}$$

注意，需要取模的只有最终得到的最大值和权值为最大值的划分方案数。您无需在计算 $\boldsymbol{A,B,C,D}$ 的过程中取模。

5
110
11010
1011010
101111011
11010101101

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

提示

样例解释

对于样例的第一组测试数据，下面分别算出 $k=1,2,3$ 时对应的答案：

• $k=1$：最大值即为它本身 $(110)_2=6$，方案数为 $1$。
• $k=2$：当划分方案为 $(11,0)$ 或 $(1,10)$ 时，都可以得到最大值，为 $(11)_2\oplus(0)_2=(1)_2\oplus(10)_2=3$，方案数为 $2$。
• $k=3$：划分方案只有 $(1,1,0)$，最大值为 $(1)_2\oplus(1)_2\oplus(0)_2=0$，方案数为 $1$。

这样可以得到 $p=\{6,3,0\},q=\{1,2,1\}$，可以分别求得 $A,B,C,D$：

$$\begin{aligned} A&=6\oplus3\oplus0=5\\ B&=1\oplus2\oplus1=2\\ C&=(6\times1)\oplus(3\times2)\oplus(0\times3)=0\\ D&=(1\times1)\oplus(2\times2)\oplus(1\times3)=6 \end{aligned}$$

故输出的数分别为 $5,2,0,6$。