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 翻译