Дана двоичная строка \(s\). Двоичная строка — это строка, состоящая из символов 0 и/или 1.
Вы можете производить следующую операцию со строкой \(s\) любое количество раз (даже ноль):
Вам нужно сделать строку \(s\) чередующейся, т. е. после выполнения операций каждые два соседних символа в \(s\) должны быть разными.
Ваша задача — вычислить два значения:
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Каждый набор входных данных состоит из одной строки, содержащей строку \(s\) (\(1 \le |s| \le 2 \cdot 10^5\)). Строка \(s\) состоит только из символов 0 и/или 1.
Дополнительное ограничение на входные данные:
Для каждого набора входных данных выведите два целых числа: минимальное количество операций, которые вам нужно выполнить, и количество различных кратчайших последовательностей операций. Поскольку второе число может быть большим, выведите его остаток по модулю \(998244353\).
В первом наборе входных данных примера кратчайшими последовательностями операций являются:
Во втором наборе входных данных примера кратчайшими последовательностями операций являются:
В третьем наборе входных данных примера единственной кратчайшей последовательностью операций является \([]\) (пустая последовательность).
3 10010 111 0101
1 2 2 6 0 1
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач