给定一个字符串 $$$s$$$,仅包含字符“0”和“1”。
您必须选择 $$$s$$$ 的连续子字符串,并从子字符串中删除所有出现的字符(该字符在其中严格少数)。
也就是说,如果子字符串中“0”的数量严格小于“1”的数量,则从子字符串中删除所有出现的“0”。如果“1”的数量严格小于“0”的数量,则删除所有出现的“1”。如果金额相同,则不执行任何操作。
您必须仅应用该操作一次。最多可以删除多少个字符?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个非空字符串 $$$s$$$,仅由字符“0”和“1”组成。 $$$s$$$ 的长度不超过 $$$2 \cdot 10^5$$$。
所有测试用例中字符串 $$$s$$$ 的总长度不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 应用一次操作后可以删除的最大字符数。
示例
输入 #1
4 01 1010101010111 00110001000 1
输出 #1
0 5 3 0
注意
在第一个测试用例中,您可以选择子字符串“0”、“1”或“01”。在“0”中,“0”的金额为$$$1$$$,“1”的金额为$$$0$$$。 “1”是严格少数,因此它的所有出现都将从子字符串中删除。然而,由于它们有 $$$0$$$,所以没有任何变化。与“1”相同。在“01”中,“0”或“1”都不是严格的少数。因此,没有任何改变。所以没有办法删除任何字符。
在第二个测试用例中,您可以选择子字符串“10101010101”。它包含 $$$5$$$ 字符“0”和 $$$6$$$ 字符“1”。 “0”是严格的少数。因此,您可以删除所有出现的情况。存在产生相同答案的其他子串。
在第三个测试用例中,您可以选择子字符串“011000100”。它包含 $$$6$$$ 字符“0”和 $$$3$$$ 字符“1”。 “1”是严格的少数。因此,您可以删除所有出现的情况。