CF2254B.Evanescent

Let $f(s)$ be the compressed version of a string $s$, formed by replacing every maximal contiguous block of identical characters with a single copy of that character. For example, $f($"aabbcc"$) \ = \ $"abc".

Let $|s|$ denote the length of a string $s$. Following this, $|f(s)|$ denotes the length of the compressed string. For example:

• $|f($"aabbcc"$)| =$ $|$"abc"$|$ $ = 3$
• If the string is empty, its length is $0$.

Yousef has given you a string $s$ consisting of $n$ lowercase Latin letters. You must delete exactly one character $s_i$ ($2 \le i \le n - 1$) to form a new string $s'$, and then find the minimum possible value of $|f(s')|$.

Note that you cannot delete $s_1$ or $s_n$.

设 $f(s)$ 为字符串 $s$ 的压缩版本，其定义为：将 $s$ 中每个最长的连续相同字符块替换为该字符的一个副本。例如，$f($"aabbcc"$) \ = \ $"abc"。

用 $|s|$ 表示字符串 $s$ 的长度。据此，$|f(s)|$ 表示压缩后字符串的长度。例如：

• $|f($"aabbcc"$)| =$ $|$"abc"$|$ $ = 3$
• 若字符串为空，则其长度为 $0$。

优素福给你一个由 $n$ 个小写拉丁字母组成的字符串 $s$。你必须恰好删除一个字符 $s_i$（其中 $2 \le i \le n - 1$），从而得到新字符串 $s'$，然后求出 $|f(s')|$ 的最小可能值。

注意：你不能删除 $s_1$ 或 $s_n$。

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

The first line of each test case contains an integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the length of the string.

The second line of each test case contains a string $s$ ($|s| = n$), consisting of lowercase Latin letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）—— 字符串的长度。

每个测试用例的第二行包含一个字符串 $s$（$|s| = n$），由小写拉丁字母组成。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the minimum possible length of the resulting compressed string after deleting one character.

对于每个测试用例，输出一个整数——删除一个字符后所得压缩字符串的最小可能长度。

In the first test case, we can only delete the character $s_2 = $ 'b', producing a string $s' = $ "ab", with $|f(s')| = 2$. Therefore, $2$ is the minimum length achievable.

In the fourth test case, we can delete the character $s_2 = $ 'b'. The resulting string is $s' = $ "aaa" with $f(s') = $ "a", so $|f(s')| = 1$.

In the sixth test case, deleting any valid character results in $f(s') = $ "e" and $|f(s')| = 1$.

In the eighth test case, we can delete the character $s_4 = $ 'c'. The resulting string is $s' = $ "abaaba" with $f(s') = $ "ababa" and $|f(s')| = 5$.

在第一个测试用例中，我们只能删除字符 $s_2 = $ 'b'，得到字符串 $s' = $ "ab"，此时 $|f(s')| = 2$。因此，可达到的最小长度为 $2$。

在第四个测试用例中，我们可以删除字符 $s_2 = $ 'b'。所得字符串为 $s' = $ "aaa"，且 $f(s') = $ "a"，故 $|f(s')| = 1$。

在第六个测试用例中，删除任意一个合法字符均使得 $f(s') = $ "e"，且 $|f(s')| = 1$。

在第八个测试用例中，我们可以删除字符 $s_4 = $ 'c'。所得字符串为 $s' = $ "abaaba"，且 $f(s') = $ "ababa"，故 $|f(s')| = 5$。