题目描述

给定一个长度为 $n$ 的由 $\mathtt{0}$ 和/或 $\mathtt{1}$ 组成的字符串 $s$。每次操作中，你可以从 $s$ 中选择一个非空子序列 $t$，要求 $t$ 中任意两个相邻字符不同。然后翻转 $t$ 中的每个字符（$\mathtt{0}$ 变为 $\mathtt{1}$，$\mathtt{1}$ 变为 $\mathtt{0}$）。例如，若 $s=\mathtt{\underline{0}0\underline{101}}$ 且 $t=s_1s_3s_4s_5=\mathtt{0101}$，操作后 $s$ 将变为 $\mathtt{\underline{1}0\underline{010}}$。

请计算将 $s$ 中所有字符变为 $\mathtt{0}$ 所需的最少操作次数。

注意：对于字符串 $s = s_1s_2\ldots s_n$，任何形如 $t=s_{i_1}s_{i_2}\ldots s_{i_k}$（$k \ge 1$）且满足 $1 \leq i_1 < i_2 < \ldots <i_k \leq n$ 的字符串都是 $s$ 的子序列。

输入格式

第一行输入包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例数量。

每个测试用例仅包含一个字符串 $s$（$1 \le |s| \le 50$），其中 $|s|$ 表示字符串长度。

输出格式

对于每个测试用例，输出将字符串 $s$ 中所有字符变为 $\mathtt{0}$ 所需的最少操作次数。

说明/提示

第一个测试用例中，你可以翻转 $s_1$。此时 $s$ 变为 $\mathtt{0}$，因此答案为 $1$。

第四个测试用例中，可以按以下顺序执行三次操作：

1. 翻转 $s_1s_2s_3s_4s_5$，此时 $s$ 变为 $\mathtt{\underline{01010}}$。
2. 翻转 $s_2s_3s_4$，此时 $s$ 变为 $\mathtt{0\underline{010}0}$。
3. 翻转 $s_3$，此时 $s$ 变为 $\mathtt{00\underline{0}00}$。

可以证明无法在少于三次操作内将 $s$ 全部变为 $\mathtt{0}$，因此答案为 $3$。

翻译由 DeepSeek R1 完成

样例

5
1
000
1001
10101
01100101011101

1
0
2
3
8