We say that a binary string (a string containing only characters '0' and '1') is pure if it does not contain either of the strings "0101" or "1010" as a subsequence.
Recall that string T is a subsequence of string S if we can delete some of the letters of S (possibly none) such that the resulting string will become T.
You are given a binary string $S$ with length $N$. We want to make this string pure by deleting some (possibly zero) characters from it. What is the minimum number of characters we have to delete?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single string $S$ with length $N$.

-----Output-----
For each test case, print a single line containing one integer — the minimum number of characters we have to delete from $S$.

-----Constraints-----
- $1 \le T \le 40$
- $1 \le N \le 1,000$
- $S$ contains only characters '0' and '1'

-----Example Input-----
4
010111101
1011100001011101
0110
111111

-----Example Output-----
2
3
0
0

-----Explanation-----
Example case 1: We can delete the first and third character of our string. There is no way to make the string pure by deleting only one character.
Example case 3: The given string is already pure, so the answer is zero.

见题面

见题面