CF1680C.Binary String

You are given a string $s$ consisting of characters 0 and/or 1.

You have to remove several (possibly zero) characters from the beginning of the string, and then several (possibly zero) characters from the end of the string. The string may become empty after the removals. The cost of the removal is the maximum of the following two values:

• the number of characters 0 left in the string;
• the number of characters 1 removed from the string.

What is the minimum cost of removal you can achieve?

给你一个仅由字符 0 和/或 1 组成的字符串 $s$。

你需要从字符串开头移除若干（可能为零）个字符，再从字符串末尾移除若干（可能为零）个字符。移除后字符串可能为空。该移除操作的代价定义为以下两个值中的最大值：

• 字符串中剩余的字符 0 的个数；
• 被移除的字符 1 的个数。

你能达到的最小代价是多少？

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

Each test case consists of one line containing the string $s$ ($1 \le |s| \le 2 \cdot 10^5$), consisting of characters 0 and/or 1.

The total length of strings $s$ in all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例由一行组成，该行包含字符串 $s$（$1 \le |s| \le 2 \cdot 10^5$），字符串 $s$ 仅由字符 0 和/或 1 组成。

所有测试用例中字符串 $s$ 的总长度不超过 $2 \cdot 10^5$。

For each test case, print one integer — the minimum cost of removal you can achieve.

对于每个测试用例，输出一个整数——你能达到的最小移除代价。

Consider the test cases of the example:

1. in the first test case, it's possible to remove two characters from the beginning and one character from the end. Only one 1 is deleted, only one 0 remains, so the cost is $1$;
2. in the second test case, it's possible to remove three characters from the beginning and six characters from the end. Two characters 0 remain, three characters 1 are deleted, so the cost is $3$;
3. in the third test case, it's optimal to remove four characters from the beginning;
4. in the fourth test case, it's optimal to remove the whole string;
5. in the fifth test case, it's optimal to leave the string as it is.

考虑示例中的测试用例：

1. 在第一个测试用例中，可以从开头删除两个字符，从结尾删除一个字符。仅删除了一个 1，仅剩下一个 0，因此代价为 $1$；
2. 在第二个测试用例中，可以从开头删除三个字符，从结尾删除六个字符。剩余两个 0，删除了三个 1，因此代价为 $3$；
3. 在第三个测试用例中，最优策略是从开头删除四个字符；
4. 在第四个测试用例中，最优策略是删除整个字符串；
5. 在第五个测试用例中，最优策略是保持字符串不变。