CF1913B.Swap and Delete

You are given a binary string $s$ (a string consisting only of 0-s and 1-s).

You can perform two types of operations on $s$:

1. delete one character from $s$. This operation costs $1$ coin;
2. swap any pair of characters in $s$. This operation is free (costs $0$ coins).

You can perform these operations any number of times and in any order.

Let's name a string you've got after performing operations above as $t$. The string $t$ is good if for each $i$ from $1$ to $|t|$ $t_i \neq s_i$ ($|t|$ is the length of the string $t$). The empty string is always good. Note that you are comparing the resulting string $t$ with the initial string $s$.

What is the minimum total cost to make the string $t$ good?

给你一个二进制字符串 $s$（仅由字符 0 和 1 组成的字符串）。

你可以在 $s$ 上执行以下两种操作：

1. 删除 $s$ 中的一个字符，该操作花费 $1$ 枚硬币；
2. 交换 $s$ 中任意两个字符，该操作免费（花费 $0$ 枚硬币）。

你可以以任意顺序、任意次数执行上述操作。

将执行若干操作后得到的字符串记为 $t$。若对每个 $i$（从 $1$ 到 $|t|$），均有 $t_i \neq s_i$（其中 $|t|$ 表示字符串 $t$ 的长度），则称字符串 $t$ 是好的。空字符串总是好的。注意：此处是将最终得到的字符串 $t$ 与初始字符串 $s$ 进行逐位比较。

使字符串 $t$ 成为好的字符串所需的最小总花费是多少？

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of each test case contains a binary string $s$ ($1 \le |s| \le 2 \cdot 10^5$; $s_i \in {$0, 1$}$) — the initial string, consisting of characters 0 and/or 1.

Additional constraint on the input: the total length of all strings $s$ doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print one integer — the minimum total cost to make string $t$ good.

对于每个测试用例，输出一个整数——使字符串 $t$ 变为“好字符串”的最小总代价。

In the first test case, you have to delete a character from $s$ to get the empty string $t$. Only then $t$ becomes good. One deletion costs $1$ coin.

In the second test case, you can, for example, delete the second character from $s$ to get the string 01, and then swap the first and second characters to get the string $t$ $=$ 10. String $t$ is good, since $t_1 \neq s_1$ and $t_2 \neq s_2$. The total cost is $1$ coin.

In the third test case, you can, for example, swap $s_1$ with $s_2$, swap $s_3$ with $s_4$, swap $s_5$ with $s_7$, $s_6$ with $s_8$ and $s_9$ with $s_{10}$. You'll get $t$ $=$ 1010001110. All swap operations are free, so the total cost is $0$.

在第一个测试用例中，你需要从 $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_{10}$，最终得到 $t = 1010001110$。所有交换操作均免费，因此总花费为 $0$。