好字符串
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
时间限制：1 Sec
内存限制：256 MB
输入文件：string.in 输出文件：string.out
对于一个二进制字符串（全部由 0 和 1 组成的字符串）$s$，小明可以做任意次下述操作：
选择 $s$ 的一个位置 $i$，将 $s_i$ 翻转（即，如果 $s_i$ 为 0，将其变为 1，如果 $s_i$ 为 1，将其变为 0）。
我们定义“好字符串”的概念：如果一个字符串 $s$ 不包含 101 和 010 这样的子序列，$s$ 就是好字符串。
例如，1001 包含 101 作为子序列，因此不是好字符串；1000 即不包含 101 也不包含 010 作为子序列，因此是好字符串。
很显然，对于任意的字符串 $s$，通过若干次上述操作，一定能将它变成好字符串（可以是 $0$ 次）。
请问，对于给定的字符串 $s$，小明至少需要执行多少次操作，才能将其变为好字符串？
注：从字符串 $s$ 中任意挑选 $0$ 个或多个字符（可以不相邻）并删除后，留下的部分叫做 $s$ 的子序列。
输入格式
第一行为一个整数 $t$，表示有 $t$ 组询问；
接下来为 $t$ 行，第 $i$ 行为第 $i$ 组询问，为一个二进制字符串 $s$。
输出格式
$t$ 行，第 $i$ 行为对第 $i$ 组询问的回答，为一个整数，表示至少需要执行多少次操作才能将对应的字符串 $s$ 变成好字符串。
样例
样例 1
7
001
100
101
010
0
1
001100
0
0
1
1
0
0
2
样例说明：
第 、、、 组询问给定的字符串已经是好字符串，答案为 次；
第 $3$ 组询问，一种可行的做法是翻转第 $1$ 个字符得到 001，答案为 $1$ 次；
第 $4$ 组询问，一种可行的做法是翻转第 $2$ 个字符得到 000，答案为 $1$ 次；
第 $7$ 组询问，一种可行的做法是翻转第 $3$、$4$ 个字符得到 000000，答案为 $2$ 次。
数据范围
$1 \le t \le 100$
令 $|s|$ 表示字符串 $s$ 的长度，有 $1 \le |s| \le 10^5$
题目保证所有询问的 $|s|$ 之和不超过 $10^5$
