Binary String

Description:

Input:

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), consisting of characters 0 and/or 1.

The total length of strings $$$s$$$ in all test cases does not exceed $$$2 \cdot 10^5$$$.

Output:

For each test case, print one integer — the minimum cost of removal you can achieve.

Sample Input:

5
101110110
1001001001001
0000111111
00000
1111

Sample Output:

1
3
0
0
0

Note:

Consider the test cases of the example:

1. in the first test case, it's possible to remove two characters from the beginning and one character from the end. Only one 1 is deleted, only one 0 remains, so the cost is $$$1$$$;
2. in the second test case, it's possible to remove three characters from the beginning and six characters from the end. Two characters 0 remain, three characters 1 are deleted, so the cost is $$$3$$$;
3. in the third test case, it's optimal to remove four characters from the beginning;
4. in the fourth test case, it's optimal to remove the whole string;
5. in the fifth test case, it's optimal to leave the string as it is.