C. Make it Alternating
combinatorics; dp; greedy
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\).
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).