给定一个由字符 0 和/或 1 组成的字符串 $$$s$$$。
您必须从字符串开头删除几个(可能为零)字符,然后从字符串末尾删除几个(可能为零)字符。删除后字符串可能会变空。移除成本是以下两个值中的最大值:
- 字符串中剩下的字符0的数量;
- 从字符串中删除的字符数 1。
您能实现的最低移除成本是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) 组成,由字符 0 和/或 1 组成。
所有测试用例中字符串$$$s$$$的总长度不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 您可以实现的最小移除成本。
示例
输入 #1
5 101110110 1001001001001 0000111111 00000 1111
输出 #1
1 3 0 0 0
注意
考虑示例的测试用例:
1. 在第一个测试用例中,可以从开头删除两个字符,从结尾删除一个字符。只删除一个1,只留下一个0,所以成本为$$$1$$$;
2. 在第二个测试用例中,可以从开头删除三个字符,从结尾删除六个字符。保留两个字符0,删除三个字符1,因此成本为$$$3$$$;
3.在第三个测试用例中,最好从开头删除四个字符;
4.在第四个测试用例中,最好删除整个字符串;
5. 在第五个测试用例中,最好保持字符串不变。