二进制字符串是由字符 $$$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$$$。