#P1879C. Make it Alternating
-
ID: 9053
Type: RemoteJudge
2000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 4
Uploaded By:
Hydro
Tags> Make it Alternating
Description
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.
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$.
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$.
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$.
3
10010
111
0101
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).