说明

时间限制：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

样例说明：

第 $1$、$2$、$5$、$6$ 组询问给定的字符串已经是好字符串，答案为 $0$ 次；

第 $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$