Бинарная строка — это строка, состоящая из символов $$$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$$$.
| Codeforces Global Round 16 |
|---|
| Закончено |
