题目描述

你有一个只由 0 和 1 构成的字符串 S 。

你需要先从 S 的开头移除若干字符，然后从 S 的结尾移除若干字符。

这样做的代价是从 S 中移除的 1 的个数和 S 中剩余 0 的个数的较大值。

请计算这个代价最小是多少。

为了减少错误做法通过本题，本题采取多组数据的方式进行测试。

输入格式

第一行一个整数 t ，表示数据组数。

接下来 t 行，每行一个字符串 S 。

输出格式

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

输入输出样例 #1

输入 #1

5
101110110
1001001001001
0000111111
00000
1111

输出 #1

1
3
0
0
0

说明/提示

样例解释

删去的部分用括号表示。下面给出对样例中的例子的构造方法。

其中有些数据构造方案不唯一。仅展示其中一种可行的构造方法。

对于第一组：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。

数据范围

$1 \le 字符串长度 \le 20000$