Shubham 有一个二进制字符串 $$$s$$$。二进制字符串是仅包含字符“0”和“1”的字符串。
他可以对字符串执行任意次数的以下操作:
- 选择字符串的索引,然后翻转该索引处的字符。这意味着,如果字符是“0”,它就会变成“1”,反之亦然。
如果一个字符串不包含“010”或“101”作为子序列,则该字符串被称为良好字符串 - 例如,“1001”包含“101”作为子序列,因此它不是一个好字符串,而“1000”既不包含“010”也不包含“101”作为子序列,因此它是一个好字符串。
他最少需要执行多少次操作才能使字符串变好?可以证明,通过这些操作,我们可以使任何字符串变得良好。
如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)字符从 $$$b$$$ 获得,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子序列。
输入
输入的第一行包含一个整数 $$$t$$$ $$$(1\le t \le 100)$$$ — 测试用例的数量。
接下来的 $$$t$$$ 行都包含一个二进制字符串 $$$s$$$ $$$(1 \le |s| \le 1000)$$$。
输出
对于每个字符串,输出使其正确所需的最少操作数。
示例
输入 #1
7 001 100 101 010 0 1 001100
输出 #1
0 0 1 1 0 0 2
注意
在测试用例 $$$1$$$、$$$2$$$、$$$5$$$、$$$6$$$ 中不需要任何操作,因为它们已经是好的字符串。
对于 $$$3$$$rd 测试用例:“001”可以通过翻转第一个字符来实现 - 并且是获得良好字符串的可能方法之一。
对于第 $$$4$$$ 测试用例:“000”可以通过翻转第二个字符来实现 - 并且是获得良好字符串的可能方法之一。
对于第 $$$7$$$ 测试用例:“000000”可以通过翻转第三个和第四个字符来实现 - 这是获得良好字符串的可能方法之一。