B. Замена и сжатие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$ длины $$$n$$$, состоящая из символов 0 и/или 1. Необходимо ровно один раз выполнить операцию, состоящую из двух шагов:

  1. выбрать не более одного символа с индексом от $$$2$$$ до $$$n-1$$$ включительно и заменить его на противоположный: 0 на 1 или 1 на 0. Можно не менять ни одного символа. Первый и последний символы строки менять нельзя;
  2. заменить каждый максимальный блок подряд идущих одинаковых символов одним таким символом.

Блок называется максимальным, если его нельзя расширить влево или вправо, добавив такой же символ. Например, после второго шага строка 100111011 превратится в 10101.

Посчитайте количество различных строк, которые могут получиться после выполнения этой операции.

Входные данные

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

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

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

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

Для каждого набора входных данных выведите одно целое число — количество различных строк, которые могут получиться после выполнения операции.

Пример
Входные данные
7
001
000
010
00010
100111011
001011010
1111
Выходные данные
1
2
2
3
3
2
2
Примечание

В первом наборе входных данных можно не менять ни одного символа или заменить второй символ. Перед сжатием получатся строки 001 и 011 соответственно. Обе строки после сжатия превратятся в 01, поэтому ответ равен $$$1$$$.

В пятом наборе входных данных:

  • если не менять ни одного символа, после сжатия получится 10101;
  • если заменить второй символ, получится 110111011, а после сжатия — 10101;
  • если заменить пятый символ, получится 100101011, а после сжатия — 1010101;
  • если заменить седьмой символ, получится 100111111, а после сжатия — 101.

Всего можно получить три различные строки: 101, 10101 и 1010101.