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

Поликарп купил новую дорогую картину и решил показать своим $$$n$$$ друзьям. Он повесил её у себя в комнате. Туда поочерёдно зашли и вышли $$$n$$$ его друзей. В один момент в комнате было не больше одного человека. Иными словами, сначала зашёл и вышел первый друг, затем второй и так далее.

Известно, что в начале (до посещения друзей) в комнате висела картина. В конце (после $$$n$$$-го друга) оказалось, что она исчезла. В какой именно момент она пропала — информации нет.

Поликарп поочерёдно опросил друзей. У каждого он спросил: была ли картина, когда тот вошёл в комнату. Каждый друг ответил одно из трёх:

  • нет (ответ кодируется символом 0);
  • да (ответ кодируется символом 1);
  • не помню (ответ кодируется символом ?).

Все, кроме вора, либо не помнят, либо сказали правду. Вор может сказать что угодно (любой из трёх вариантов).

Поликарп не может понять, кто вор. Он просит вас узнать количество тех, кого можно считать вором в соответствии показаниями.

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

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

Далее следуют описания наборов входных данных.

В первой строке каждого наборов содержится одна непустая строка $$$s$$$ (ей длина не превосходит $$$2 \cdot 10^5$$$) — описания ответов друзей, где $$$s_i$$$ обозначает ответ $$$i$$$-го друга. Каждый символ в строке это либо 0, либо 1, либо ?.

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

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

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

Вывести одно положительное (строго большее нуля) число – количество друзей, которые могли украсть картину на основании данных показаний.

Пример
Входные данные
8
0
1
1110000
?????
1?1??0?0
0?0???
??11
??0??
Выходные данные
1
1
2
5
4
1
1
3
Примечание

В первом случае ответ равен $$$1$$$, так как у нас был ровно $$$1$$$ друг.

Во втором случае аналогично.

В третьем случае подозреваемыми являются третий и четвёртый друг (считаем с единицы). Можно показать, что никто другой не мог быть вором.

В четвёртом случае нам абсолютно ничего не известно, поэтому подозреваем всех.