A16435. 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?

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$ .

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

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$ .