Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

greedy

*1300

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Make it Alternating

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$.

Example

Input

3100101110101

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2023 05:28:23 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|