CF1363B Subsequence Hate

Shubham 有一个二进制字符串 $s$。二进制字符串是仅包含字符 “0” 和 “1” 的字符串。 他可以对字符串进行如下操作任意次： - 选择字符串中的一个下标，并翻转该位置的字符。也就是说，如果该字符是 “0”，则变为 “1”；如果是 “1”，则变为 “0”。 如果一个字符串不包含 “010” 或 “101” 作为子序列，则称其为好字符串。例如，“1001” 包含 “101” 作为子序列，因此不是好字符串；而 “1000” 不包含 “010” 或 “101” 作为子序列，因此是好字符串。 请问他最少需要进行多少次操作，才能使字符串变为好字符串？可以证明，通过这些操作可以将任意字符串变为好字符串。 如果字符串 $a$ 可以通过从字符串 $b$ 中删除若干（可能为零或全部）字符得到，则称 $a$ 是 $b$ 的一个子序列。

输入的第一行包含一个整数 $t$，表示测试用例的数量，$1 \le t \le 100$。 接下来的 $t$ 行，每行包含一个二进制字符串 $s$，$1 \le |s| \le 1000$。

对于每个字符串，输出使其变为好字符串所需的最小操作次数。

在第 $1$、$2$、$5$、$6$ 个测试用例中，字符串本身已经是好字符串，因此不需要进行任何操作。 对于第 $3$ 个测试用例：“001” 可以通过翻转第一个字符得到，这是将字符串变为好字符串的一种方式。 对于第 $4$ 个测试用例：“000” 可以通过翻转第二个字符得到，这是将字符串变为好字符串的一种方式。 对于第 $7$ 个测试用例：“000000” 可以通过翻转第三和第四个字符得到，这是将字符串变为好字符串的一种方式。 由 ChatGPT 4.1 翻译