给你一个二进制字符串$$$s$$$。二进制字符串是由字符 0 和/或 1 组成的字符串。
您可以对 $$$s$$$ 执行以下操作任意次数(甚至零次):
- 选择一个整数 $$$i$$$,使得 $$$1 \le i \le |s|$$$,然后删除字符 $$$s_i$$$。
你必须让 $$$s$$$ 交替出现,即。 e.执行该操作后,$$$s$$$ 中每两个相邻的字符应该不同。
您的目标是计算两个值:
- 使 $$$s$$$ 交替所需的最少操作数;
- 使 $$$s$$$ 交替的不同最短操作序列的数量。如果在至少一个操作中,所选整数 $$$i$$$ 在这两个序列中不同,则两个操作序列是不同的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) 组成。字符串 $$$s$$$ 仅包含字符 0 和/或 1。
输入的附加约束:
- 所有测试用例中字符串 $$$s$$$ 的总长度不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印两个整数:必须执行的最小操作数,以及不同的最短操作序列的数量。由于第二个数字可能很大,因此打印其对 $$$998244353$$$ 取模后的余数。
示例
输入 #1
3 10010 111 0101
输出 #1
1 2 2 6 0 1
注意
在示例的第一个测试用例中,最短的操作序列是:
- $$$[2]$$$(删除$$$2$$$第一个字符);
- $$$[3]$$$(删除$$$3$$$-rd 字符)。
在示例的第二个测试用例中,最短的操作序列是:
- $$$[2, 1]$$$(删除$$$2$$$-第一个字符,然后删除$$$1$$$-第一个字符);
- $$$[2, 2]$$$;
- $$$[1, 1]$$$;
- $$$[1, 2]$$$;
- $$$[3, 1]$$$;
- $$$[3, 2]$$$.
在示例的第三个测试用例中,唯一最短的操作序列是 $$$[]$$$ (空序列)。