解题思路

给定仅由 0/1 组成的字符串 s。操作允许：

• 删除任意字符（代价 1 枚硬币）
• 交换任意两个字符（免费）

我们要得到某个字符串 t，满足对所有 i ∈ [1, |t|] 都有 t_i ≠ s_i。交换免费意味着：在删除若干字符后，剩余字符的相对顺序不重要，我们只需关心剩余 0/1 的数量是否能在前 |t| 个位置与 s 的前 |t| 位逐一相反。

设：

题目内容

多多在玩一个特殊的消消乐游戏。在游戏中有一个仅由 $0$ 和 $1$ 组成的字符串 $s$ ，多多只被允许做以下两种操作：

从字符串 $s$ 中删除任意一个字符。这个操作将花费 $1$ 枚硬币；

交换字符串 $s$ 中的任意两个字符。这个操作是完全免费，即不花费硬币。

现在要求多多经过上述任意多次操作，最终得到一个字将串 $t$ 。如果字符串 $t$ 满足对于从 $1$ 到 $丨t丨$( $丨t丨$ 表示字将串 $t$ 的长度)位置的字符 $t_i$ 始终有 $t_i≠s_i$ , 那么称字符串 $t$ 为一个“漂亮的字符串”(其中空字符串也被认为是一个漂亮的字符串)。

多多现在想知道最少需要花费多少枚硬币才可以得到一个漂亮的字符串。

输入描述

第一行包含一个整数 $t(1<=t<= 10^4)$,表示有 $1$ 组测试数据

每组测试数据包含一个由数字 $0$ 和 $1$ 构成的字符串 $s$ ，其中字符串 $s$ 的长度满足 $(1 <= 丨s丨<=2*10^5)$

输出描述

对于每组测试数据输出一个整数，代表最少需整花费多少枚硬币才可以得到一个“漂亮的字符串“ 。

样例1

输入

4
0
011
0101110001
111100

输出

1
1
0
4

说明

第一组测试用例中，只能删除原字符串 $0$ 得到一个空的漂亮字符串，即花费 $1$ 枚硬币；

第二组测试用例中，可以先删除最后一个字符 $1$ 得到一个字符串 $01$，然后再交换第一个和第二个字符的位置，得到一个亮字符串 $10$、总共花费 $1$ 枚硬币；

第三组测试用例中，分别交换 $1$ 和 $2$，$3$ 和 $4$ ，$5$ 和 $7$，$6$ 和 $8$，$9$ 和 $10$ 位置的字符，可以得到一个漂亮的字符串 $1010001110$ 。总共花费 $0$ 枚硬币；

第四组测试用例中，删除前 $4$ 个字符串可以得到一个漂亮的字符串 $00$ 。总共花费 $4$ 枚硬币。