310744: CF1879C. Make it Alternating

C. Make it Alternatingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a binary string $s$. A binary string is a string consisting of characters 0 and/or 1.

You can perform the following operation on $s$ any number of times (even zero):

• choose an integer $i$ such that $1 \le i \le |s|$, then erase the character $s_i$.

You have to make $s$ alternating, i. e. after you perform the operations, every two adjacent characters in $s$ should be different.

Your goal is to calculate two values:

• the minimum number of operations required to make $s$ alternating;
• the number of different shortest sequences of operations that make $s$ alternating. Two sequences of operations are different if in at least one operation, the chosen integer $i$ is different in these two sequences.

Input

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of one line containing the string $s$ ($1 \le |s| \le 2 \cdot 10^5$). The string $s$ consists of characters 0 and/or 1 only.

Additional constraint on the input:

• the total length of strings $s$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, print two integers: the minimum number of operations you have to perform, and the number of different shortest sequences of operations. Since the second number might be large, print its remainder modulo $998244353$.

ExampleInput

3
10010
111
0101

Output

1 2
2 6
0 1

Note

In the first test case of the example, the shortest sequences of operations are:

• $[2]$ (delete the $2$-nd character);
• $[3]$ (delete the $3$-rd character).

In the second test case of the example, the shortest sequences of operations are:

• $[2, 1]$ (delete the $2$-nd character, then delete the $1$-st character);
• $[2, 2]$;
• $[1, 1]$;
• $[1, 2]$;
• $[3, 1]$;
• $[3, 2]$.

In the third test case of the example, the only shortest sequence of operations is $[]$ (empty sequence).

题目大意：给定一个由字符 '0' 和 '1' 组成的二进制字符串 s。你可以对 s 进行任意次数（包括零次）的操作：选择一个整数 i（1 ≤ i ≤ |s|），然后擦除字符 s_i。你的目标是通过这些操作使得 s 变成交替的，即操作后 s 中的每两个相邻字符都不同。需要计算两个值：使 s 交替所需的最小操作次数，以及使 s 交替的不同最短操作序列的数量（两个操作序列如果至少在一个操作中选择的整数 i 不同，则视为不同）。输出每个测试用例的最小操作次数和不同最短操作序列的数量（第二个数对 998244353 取模）。

输入数据格式：第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。每个测试用例包含一行，是一个字符串 s（1 ≤ |s| ≤ 2 × 10^5），s 仅由字符 '0' 和 '1' 组成。所有测试用例中字符串 s 的总长度不超过 2 × 10^5。

输出数据格式：对于每个测试用例，输出两个整数：所需的最小操作次数和不同的最短操作序列的数量（第二个数对 998244353 取模）。

例如：
```
输入：
3
10010
111
0101

输出：
1 2
2 6
0 1
```题目大意：给定一个由字符 '0' 和 '1' 组成的二进制字符串 s。你可以对 s 进行任意次数（包括零次）的操作：选择一个整数 i（1 ≤ i ≤ |s|），然后擦除字符 s_i。你的目标是通过这些操作使得 s 变成交替的，即操作后 s 中的每两个相邻字符都不同。需要计算两个值：使 s 交替所需的最小操作次数，以及使 s 交替的不同最短操作序列的数量（两个操作序列如果至少在一个操作中选择的整数 i 不同，则视为不同）。输出每个测试用例的最小操作次数和不同最短操作序列的数量（第二个数对 998244353 取模）。 输入数据格式：第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。每个测试用例包含一行，是一个字符串 s（1 ≤ |s| ≤ 2 × 10^5），s 仅由字符 '0' 和 '1' 组成。所有测试用例中字符串 s 的总长度不超过 2 × 10^5。 输出数据格式：对于每个测试用例，输出两个整数：所需的最小操作次数和不同的最短操作序列的数量（第二个数对 998244353 取模）。 例如： ``` 输入： 3 10010 111 0101 输出： 1 2 2 6 0 1 ```