题目描述

你会得到一个 $t$，代表 $t$ 个测试样例，每个测试样例都有一个长度为 $n$ 的，并且只由 0 和 1 组成的字符串 $s$。

• $A(s)$ 是 $s$ 这个字符串的子串与 01 相等的个数。
• $B(s)$ 是 $s$ 这个字符串的子串与 10 相等的个数。

例如 010 这个字符串，它的 $A(s)=1,B(s)=1$。

憨憨最喜欢平衡了，所以它希望 $s$ 这个字符串中的 $A(s)$ 和 $B(s)$ 相等。现在你可以修改这个字符串(0 改成 1，或者 1 变成 0)，使这个字符串的 $A(s)$ 和 $B(s)$ 相等。现在憨憨想要请你帮他想想最少修改几次可以使 $A(s)$ 和 $B(s)$ 相等。

输入格式

第一行包含一个整数 $T\ (1 ≤ T ≤ 2*10^5)$，表示测试用例的数量。

每组样例格式如下：

• 一行由 0 和 1 组成的字符串，字符串长度不超过 $200$。

输出格式

输出 $T$ 行，每行一个整数，表示答案。

3
1
01
010

0
1
0