C. Чередуй!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана двоичная строка $$$s$$$. Двоичная строка — это строка, состоящая из символов 0 и/или 1.

Вы можете производить следующую операцию со строкой $$$s$$$ любое количество раз (даже ноль):

  • выбрать целое число $$$i$$$ такое, что $$$1 \le i \le |s|$$$, затем удалить символ $$$s_i$$$.

Вам нужно сделать строку $$$s$$$ чередующейся, т. е. после выполнения операций каждые два соседних символа в $$$s$$$ должны быть разными.

Ваша задача — вычислить два значения:

  • минимальное количество операций, необходимых для того, чтобы сделать строку $$$s$$$ чередующейся;
  • количество различных кратчайших последовательностей операций, которые делают строку $$$s$$$ чередующейся. Две последовательности операций считаются различными, если хотя бы в одной операции выбранное целое число $$$i$$$ отличается в этих двух последовательностях.
Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из одной строки, содержащей строку $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$). Строка $$$s$$$ состоит только из символов 0 и/или 1.

Дополнительное ограничение на входные данные:

  • суммарная длина строк $$$s$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Выходные данные

Для каждого набора входных данных выведите два целых числа: минимальное количество операций, которые вам нужно выполнить, и количество различных кратчайших последовательностей операций. Поскольку второе число может быть большим, выведите его остаток по модулю $$$998244353$$$.

Пример
Входные данные
3
10010
111
0101
Выходные данные
1 2
2 6
0 1
Примечание

В первом наборе входных данных примера кратчайшими последовательностями операций являются:

  • $$$[2]$$$ (удалить $$$2$$$-й символ);
  • $$$[3]$$$ (удалить $$$3$$$-й символ).

Во втором наборе входных данных примера кратчайшими последовательностями операций являются:

  • $$$[2, 1]$$$ (удалить $$$2$$$-й символ, затем удалить $$$1$$$-й символ);
  • $$$[2, 2]$$$;
  • $$$[1, 1]$$$;
  • $$$[1, 2]$$$;
  • $$$[3, 1]$$$;
  • $$$[3, 2]$$$.

В третьем наборе входных данных примера единственной кратчайшей последовательностью операций является $$$[]$$$ (пустая последовательность).