题目描述

147学长最近获得了一个由字符 0 和 1 组成的字符串S。他对这个字符串很是喜爱，以至于他总想对这个字符串做点什么

于是，147想到了一个骚操作：

147从字符串的开头删除了几个（可能是零个）字符，然后又从字符串的末尾删除了几个（可能是零个）字符。删除后，字符串可能会变为空。147是一个做事总是考虑成本的人，所以他定义删除的成本是以下两个值中的最大值：

• 字符串中剩余的字符0的个数;
• 从字符串中删除的字符1的个数。

请问147可以达到的最小删除成本是多少？

输入形式

第一行包含一个整数t ($1\leq t\leq5*10^3$） — 测试用例的数量。

每个测试用例由一行由一个字符串S组成($1\leq |S|\leq2*10^5$)，由字符 0 和 1 组成。

|S|表示字符串S的长度

保证每个测试样例的字符串的总长度不会超过$2*10^5$

输出形式

对于每个测试用例，打印一个整数 — 147可以实现的最小删除成本。

样例

5
101110110
1001001001001
0000111111
00000
1111

1
3
0
0
0

样例解释

在第一个测试用例中，可以从开头删除两个字符，从末尾删除一个字符。只有一个 1 被删除，只剩下一个 0，所以成本是1;

在第二个测试用例中，可以从开头删除三个字符，从末尾删除六个字符。保留两个字符 0，删除三个字符 1，因此成本为3;

在第三个测试用例中，最好从开头删除四个字符;

在第四个测试用例中，最好删除整个字符串;

在第五个测试用例中，最好将字符串保持原样。