题目描述

王老师有一个只包含 0 和 1 的字符串 S。

王老师准备对字符串 S 进行如下操作：

先从 字符串的开头 移除若干个字符（可以为 0 个）。 再从 字符串的结尾 移除若干个字符（可以为 0 个）。 操作后，S 会变成一个连续的子串（可以是原串或者空串，但空串通常不会有最小代价意义）。

定义本次操作的代价为：

移除的 1 的个数 与 剩余字符串中的 0 的个数，两者中的较大值。 请你帮王老师计算： 所有可能的操作方式中，最小的代价是多少？

输入格式

第一行一个整数 t，表示数据组数。 接下来 t 行，每行一个字符串 S。

输出格式

对每组数据，输出一个整数表示最小代价。

样例输入 1

5
101110110
1001001001001
0000111111
00000
1111

样例输出 1

1
3
0
0
0

样例输入 2

见题目中的大样例数据cost.in 样例输出 2

见题目中的大样例数据cost.out 提示/说明

大样例数据下载

（记得解压）

样例解释

删去的部分用括号表示

下面给出对样例中的例子的构造方法，其中有些数据构造方案不唯一，仅展示其中一种可行的构造方法。

第一组：101110110 -> (10)111011(0) 移除的 1 有 1 个，剩余的 0 有 1 个，较大值为 1

第二组：1001001001001 -> (100100)1001(001) 移除的 1 有 3 个，剩余的 0 有 2 个，较大值为 3

第三组：0000111111 -> (0000)111111() 移除的 1 有 0 个，剩余的 0 有 0 个，较大值为 0

第四组：00000 -> (00000)() 移除的 1 有 0 个，剩余的 0 有 0 个，较大值为 0

第五组：1111 -> ()1111() 移除的 1 有 0 个，剩余的 0 有 0 个，较大值为 0

数据范围

共 10 个测试点，每个测试点 10 分。

测试点编号 t 数据范围 字符串长度 len 其他说明

1 ~ 3 $1≤t≤10$ $1≤len≤100$ 无
4 ~ 5 $1≤t≤10$ $1≤len≤20,000$ 每个字符串中 1 的数量不超过 10 个
6 ~ 7 $1≤t≤10$ $1≤len≤20,000$ 每个字符串中 0 的数量不超过 10 个
8 ~ 10 $1≤t≤10$ $1≤len≤20,000$ 无