给定一个01串s，可以对串s进行如下两种操作：
1.删除一个字符。（花费一枚金币）
2.交换某两个字符的位置。（不花费金币）
假设经过若干次操作后得到的字符串为t。
定义t是good串当且仅当对于任意的i（1≤i≤|t|，|t|为字符串t 的长度），均满足ti≠si（s是原本的字符串）。当然，空串也是good串。
现在请你帮忙计算一下,串s最少需要花费多少金币才能得到good串t。

第一行为整数T,表示有T (1≤T≤10000)组测试样例。
每组测试样例为一个仅有0与1组成的字符串s(1≤|s|≤200000)。
测试数据保证所有字符串长度之和不超过200000。

对于每组测试样例，仅输出一个整数k，表示得到good串所需的最小花费。

4
0
011
0101110001
111100

1
1
0
4

在测试样例1中，需要在s中删除一个字符后变为空串t，因此最小花费为1。
在测试样例2中，可以进行如下操作：在s中删除一个字符后使串t变为"01"，然后交换位置得到"10",因此最小花费为1。
在测试样例3中,可以进行如下操作：交换s1与s2;交换s3与s4;交换s5与s7;交换s6与s8;交换s9与s10;得到t="1010001110"；因此最小花费为0。