CF1879C Make it Alternating

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).