给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,由 $$$\mathtt{0}$$$ 和/或 $$$\mathtt{1}$$$ 组成。在一次操作中,您可以从 $$$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$$$ 的长度。
输出
对于每个测试用例,输出将 $$$s$$$ 中的所有字符更改为 $$$\mathtt{0}$$$ 所需的最少操作数。
示例
输入 #1
5 1 000 1001 10101 01100101011101
输出 #1
1 0 2 3 8
注意
在第一个测试用例中,您可以翻转$$$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}$$$。
可以看出,在少于 3 次操作中无法将 $$$s$$$ 中的所有字符更改为 $$$\mathtt{0}$$$,因此答案为 $$$3$$$。