B. MIN-MEX разрез
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бинарная строка — это строка, состоящая из символов $$$0$$$ и $$$1$$$.

Определим $$$\operatorname{MEX}$$$ бинарной строки как наименьшую из цифр $$$0$$$, $$$1$$$ или $$$2$$$, которая не встречается в этой строке. Например, $$$\operatorname{MEX}$$$ строки $$$001011$$$ — это $$$2$$$, потому что $$$0$$$ и $$$1$$$ встречаются хотя бы один раз. $$$\operatorname{MEX}$$$ строки $$$1111$$$ — это $$$0$$$, потому что $$$0$$$ и $$$2$$$ не встречаются ни разу, и $$$0 < 2$$$.

Дана бинарная строка $$$s$$$. Необходимо разбить её на произвольное количество подстрок так, чтобы каждая её цифра принадлежала ровно одной подстроке. Строку разрешается разбить на одну подстроку — эту строку целиком.

Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

Какую минимальную сумму $$$\operatorname{MEX}$$$ всех полученных подстрок можно получить?

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

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

Каждый набор входных данных содержит единственную бинарную строку $$$s$$$ ($$$1 \le |s| \le 10^5$$$).

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

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

Для каждого набора входных данных выведите единственное целое число — наименьшую сумму $$$\operatorname{MEX}$$$, которую можно получить, разбив $$$s$$$ на подстроки оптимально.

Пример
Входные данные
6
01
1111
01100
101
0000
01010
Выходные данные
1
0
2
1
1
2
Примечание

В первом наборе входных данных минимальная сумма равна $$$\operatorname{MEX}(0) + \operatorname{MEX}(1) = 1 + 0 = 1$$$.

Во втором наборе входных данных минимальная сумма равна $$$\operatorname{MEX}(1111) = 0$$$.

В третьем наборе входных данных минимальная сумма равна $$$\operatorname{MEX}(01100) = 2$$$.