题目描述

Bob 有一个 01 串 $S$，定义其一个子串 $[l,r]$ 的权重为：$\max\left(\sum_{i\in[l,r]}[S_i=0],\sum_{i\notin[l,r]}[S_i=1]\right)$，也就是子串中 $0$ 的个数与子串外 $1$ 的个数的较大值。

请求出所有子串的最小权重。在本题中，子串可以为空，其对应权重即为 $S$ 中 $1$ 的个数。

输入格式

第一行一个整数 $T$ 表示数据组数，对于每组数据：

一行一个 01 串 $S$。

输出格式

对于每组数据，输出一行一个整数表示答案。

3
0011100
0101010
1101011

0
1
2

样例解释 1

对于第一组数据，子串S[3,5]="111"的权重为0。 对于第二组数据，子串S[2,4]="101"的权重为1。 对于第三组数据，子串S[1,5]="11010"的权重为2。

数据范围

对于 $30\%$ 的数据，$\sum |S|\leq 100$。

对于 $60\%$ 的数据，$\sum |S|\leq 5000$。

对于 $100\%$ 的数据，$1\leq T\leq 10^4$，$1\leq |S|,\sum |S|\leq 2\times 10^5$。