给定一个二进制字符串 $$$s$$$ (仅由 0 和 1 组成的字符串)。
您可以对$$$s$$$执行两种类型的操作:
1. 从$$$s$$$中删除一个字符。此操作需要花费$$$1$$$硬币;
2. 交换$$$s$$$中的任意一对字符。此操作是免费的(花费 $$$0$$$ 硬币)。
您可以按任意顺序执行这些操作任意次数。
让我们将执行上述操作后得到的字符串命名为$$$t$$$。如果对于从 $$$1$$$ 到 $$$|t|$$$ $$$t_i \neq s_i$$$ 的每个 $$$i$$$ 字符串 $$$t$$$ 是好的($$$|t|$$$ 是字符串 $$$t$$$ 的长度)。空字符串总是好的。请注意,您正在将结果字符串 $$$t$$$ 与初始字符串 $$$s$$$ 进行比较。
使字符串 $$$t$$$ 变得良好的最小总成本是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例的唯一行包含一个二进制字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$; $$$s_i \in \{$$$0, 1$$$\}$$$) - 初始字符串,由字符 0 和/或 1 组成。
对输入的附加限制:所有字符串 $$$s$$$ 的总长度不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 使字符串 $$$t$$$ 良好的最小总成本。
示例
输入 #1
4 0 011 0101110001 111100
输出 #1
1 1 0 4
注意
在第一个测试用例中,您必须从 $$$s$$$ 中删除一个字符才能得到空字符串 $$$t$$$。只有这样$$$t$$$ 才变得好。删除一次需要花费 $$$1$$$ 硬币。
在第二个测试用例中,例如,您可以从 $$$s$$$ 中删除第二个字符以获取字符串 01,然后交换第一个和第二个字符以获取字符串 $$$t$$$ $$$=$$$ 10. 字符串 $$$t$$$ 很好,因为 $$$t_1 \neq s_1$$$ 和 $$$t_2 \neq s_2$$$。总成本为 $$$1$$$ 硬币。
在第三个测试用例中,例如,您可以将 $$$s_1$$$ 与 $$$s_2$$$ 交换、$$$s_3$$$ 与 $$$s_4$$$ 交换、$$$s_5$$$ 与 $$$s_7$$$ 交换、$$$s_6$$$ 与 $$$s_8$$$ 交换、$$$s_9$$$ 与 $$$s_9$$$ 交换。 $$$s_{10}$$$。您将获得 $$$t$$$ $$$=$$$ 1010001110。所有交换操作都是免费的,因此总成本为 $$$0$$$。