题目描述

一个二进制字符串是只包含字符 $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$ 的开头和结尾删除若干（可能为零或全部）字符得到。

请问，将 $s$ 最优切分后，各个子串的 $\operatorname{MEX}$ 之和的最小值是多少？

输入格式

输入包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来每个测试用例包含一行二进制字符串 $s$（$1 \le |s| \le 10^5$）。

保证所有测试用例中字符串 $s$ 的总长度不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数，表示将 $s$ 最优切分后，各个子串的 $\operatorname{MEX}$ 之和的最小值。

说明/提示

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

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

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

由 ChatGPT 4.1 翻译

样例

6
01
1111
01100
101
0000
01010

1
0
2
1
1
2