← 返回题目列表

Codeforces · 1566/B

B. MIN-MEX 剪切

中文机器翻译题面 查看原题

二进制字符串是由字符 $$$0$$$ 和 $$$1$$$ 组成的字符串。

令二进制字符串的 $$$\operatorname{MEX}$$$ 为 $$$0$$$、$$$1$$$ 或 $$$2$$$ 中未出现在字符串中的最小数字。例如,$$$001011$$$ 的 $$$\operatorname{MEX}$$$ 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 在字符串中至少出现一次,$$$1111$$$ 的 $$$\operatorname{MEX}$$$ 是 $$$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$$$。

输出

对于每个测试用例,打印一个整数 - 通过最佳切割 $$$s$$$ 可以获得的所有子字符串 $$$\operatorname{MEX}$$$ 的最小和。

示例

输入 #1

6
01
1111
01100
101
0000
01010

输出 #1

1
0
2
1
1
2

注意

在第一个测试用例中,最小总和为 $$$\operatorname{MEX}(0) + \operatorname{MEX}(1) = 1 + 0 = 1$$$。

在第二个测试用例中,最小总和为 $$$\operatorname{MEX}(1111) = 0$$$。

在第三个测试用例中,最小总和为 $$$\operatorname{MEX}(01100) = 2$$$。