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):
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 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:
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$$$.
1 2 2 6 0 1
In the first test case of the example, the shortest sequences of operations are:
In the second test case of the example, the shortest sequences of operations are:
In the third test case of the example, the only shortest sequence of operations is $$$$$$ (empty sequence).