### 问题描述 星迪是一个热爱密码学的小学生，在二进制的世界里，他发现了一种特别的密码规则。一个二进制字符串被星迪称为“优美的密码”，当且仅当它包含相同数量的 $01$ 和 $10$ 子字符串。需要注意的是，这些子字符串可能会重叠。例如，字符串 $1101001$ 就是一个“优美的密码”， 现在，星迪手里有一个二进制的密码，他想试着改变这个密码的某一位，看能否得到一个“优美的密码”。你能帮助星迪找出原密码中有多少个位置的数字可以更改吗？改变这个位置的数字是指，如果这个位置的数字是 `0`，就改为 `1`；如果这个位置的数字是 `1`，就改为 `0`。 ### 输入格式 第一行输入一个整数 $T$ —— 测试用例的数量。然后是 $T$ 个测试用例。 每个测试用例的第二行包含一个只包含 `0` 和 `1` 的二进制字符串 $S$。 数据范围保证： - $1 \leq T \leq 10^3$。 - $2 \leq |S| \leq 2 \times 10^5$。 - 所有测试用例中 $S$ 的总长度不超过 $2 \times 10^5$。 ### 输出格式 对于每个测试用例，输出在单独的一行上，给出原密码中有多少个位置的数字可以更改后得到一个“优美的密码”。 ### 样例输入 ```text 2 10100 11111 ``` ### 样例输出 ```text 2 3 ``` ### 说明 在第一个测试用例中： 当 $i = 1$ 时，更改 $S_i$ 后得到的字符串是 `00100`，这是一个“优美的密码”，因为它有一个 `01` 和一个 `10`。 当 $i = 5$ 时，更改 $S_i$ 后得到的字符串是 `10101`，这也是一个“优美的密码”，因为它有两个 `01` 和两个 `10`。 可以证明，对于 $i = 2, 3, 4$，更改 $S_i$ 后不会得到“优美的密码”。 因此，在这个测试用例中，可以更改的位置数目为 $2$。