AT_abc426_d [ABC426D] Pop and Insert

给定一个长度为 $N$ 只包含 `0` 和 `1` 的字符串 $S$。 你可以对 $S$ 任意次（可以为零次）执行以下操作： - 删除第一个或最后一个字符，将其翻转（将 `0` 变成 `1`，将 `1` 变成 `0`），并插入回任意位置。更严格地说，设 $r($`0`$) = $`1`，$r($`1`$) = $`0`，你可以执行以下两种选择之一（其中 $S_i$ 表示第 $i$ 个字符）： - 任选 $i\ (1\leq i\leq N)$，将 $S$ 变为 $S_2\dots S_i\,r(S_1)\,S_{i+1}\dots S_N$。 - 任选 $i\ (0\leq i\leq N-1)$，将 $S$ 变为 $S_1\dots S_i\,r(S_N)\,S_{i+1}\dots S_{N-1}$。 请计算，最少需要多少次操作才能使 $S$ 的所有字符都相同。可以证明，总能通过合法操作使 $S$ 全部变为相同字符。 有 $T$ 组测试数据，请依次解决。

输入按如下格式给出： > $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ $\text{case}_i$ 表示第 $i$ 组测试数据，格式如下： > $N$ $S$

输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

### 样例解释 1 对于第一组数据，例如，可以按如下方式通过四次操作将所有字符变为 `0`。无法用三次或更少次数完成，因此答案为 $4$。 - 删除首位字符 `0`，并将其（翻转为 `1` 后）插入到第一个和第二个字符之间（删除后 $S$ 的位置）。此时 $S$ 变为 `11001`。 - 删除首位字符 `1`，并将其（翻转为 `0` 后）插入到第二和第三个字符之间。$S$ 变为 `10001`。 - 删除尾部字符 `1`，并将其（翻转为 `0` 后）插入到末尾。$S$ 变为 `10000`。 - 删除首位字符 `1`，并将其（翻转为 `0` 后）插入到开头。$S$ 变为 `00000`。 对于第二组数据，$S$ 的所有字符一开始就是相同的，因此不需要任何操作。 ### 数据范围 - $1\leq T\leq 2\times 10^5$ - $2\leq N \leq 5\times 10^5$ - $T$ 和 $N$ 为整数。 - $S$ 是长度为 $N$ 只包含 `0` 和 `1` 的字符串。 - 所有测试数据中 $N$ 的总和不超过 $5\times 10^5$。 由 ChatGPT 5 翻译