给你一个二进制字符串$$$^{\dagger}$$$。请找出需要将其切成的最小块数,以便将所得块重新排列成排序的二进制字符串。
请注意:
- 每个角色必须恰好位于其中一个棋子中;
- 这些片段必须是原始字符串的连续子串;
- 您必须使用重新排列中的所有棋子。
$$$^{\dagger}$$$ 二进制字符串是由字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ 组成的字符串。排序的二进制字符串是这样的二进制字符串:所有字符 $$$\texttt{0}$$$ 都位于所有字符 $$$\texttt{1}$$$ 之前。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。
每个测试用例的唯一行包含单个字符串 $$$s$$$ ($$$1 \leq |s| \leq 500$$$),由字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ 组成,其中 $$$|s|$$$ 表示字符串 $$$s$$$ 的长度。
输出
对于每个测试用例,输出一个整数 - 能够将字符串重新排列成排序的二进制字符串所需的最小数量。
示例
输入 #1
6 11010 00000000 1 10 0001111 0110
输出 #1
3 1 1 2 1 2
注意
第一个测试用例如声明中所示。可以证明你不能使用少于 $$$3$$$ 的块。
在第二个和第三个测试用例中,二进制字符串已经排序,因此只需要 $$$1$$$ 块。
在第四个测试用例中,您需要在两个字符之间进行一次剪切并重新排列它们以形成字符串 $$$\texttt{01}$$$。