题目描述

每次测试的时间限制：$1$ 秒 每次测试的内存限制：$512$ 兆字节

给定一个长度为 $n$ 的字符串 $s$，由 $0$ 和/或 $1$ 组成。在一次操作中，你可以从 $s$ 中选择一个非空子序列 $t$，使得 $t$ 中任意两个相邻字符不同。然后，翻转 $t$ 中的每个字符（$0$ 变成 $1$，$1$ 变成 $0$）。例如，若 $s = \texttt{0}\underline{\texttt{0}}\texttt{1}\underline{\texttt{0}}\underline{\texttt{1}} $（下划线表示选中的字符）且 $t = s_1 s_3 s_4 s_5 = \texttt{0101}$，操作后 $s$ 变为 $\texttt{1}\underline{\texttt{0}}\texttt{0}\underline{\texttt{1}}\underline{\texttt{0}} $。

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

回忆：对于字符串 $s = s_1 s_2 \dots s_n$，任何满足 $1 \le i_1 < i_2 < \dots < i_k \le n$（$k \ge 1$）的字符串 $t = s_{i_1} s_{i_2} \dots s_{i_k}$ 都是 $s$ 的一个子序列。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 输入测试用例的数量。 每个测试用例仅一行，包含字符串 $s$（$1 \le |s| \le 50$），其中 $|s|$ 表示 $s$ 的长度。

输出格式

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

5
1
000
1001
10101
01100101011101

1
0
2
3
8

注意

在第一个测试用例中，你可以翻转 $s_1$。然后 $s$ 变为 $0$，所以答案是 $1$。

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

翻转 $s_1 s_2 s_3 s_4 s_5$。此时 $s$ 变为 $\underline{0}\underline{1}\underline{0}\underline{1}\underline{0}$。

翻转 $s_2 s_3 s_4$。此时 $s$ 变为 $0\underline{0}\underline{1}\underline{0}0$。

翻转 $s_3$。此时 $s$ 变为 $00\underline{0}00$。

可以证明，无法在少于三次操作内将 $s$ 中所有字符变为 $0$，因此答案是 $3$。