7unar的消消乐

背景

7unar 上数据结构课摸鱼的时候，偷偷打开了手机上一款叫「字符消消乐」的小游戏。

屏幕上有一排共 $n$ 个彩色方块，每个方块上写着一个小写字母。

游戏的消除规则很简单：相邻且字母相同的方块会自动合并成一个，这个过程会一直进行，直到没有相邻相同的方块为止——最后剩下的方块序列就是你的最终得分依据。

然而 7unar 背包里藏着一件神器——「拆迁锤」（只能用一次！）。

它可以精准砸掉中间某一个方块（首尾两个不能砸，砸了屏幕就裂了，7unar 还不想换手机屏）。

方块被砸碎后，左右两边的方块自然会靠拢——这时候，原本被隔开的相同字母可能就凑到一起了！

7unar 心想：就一次机会，用完拆迁锤之后，最少能剩几个方块？

题目描述

定义 $f(s)$ 为字符串 $s$ 的压缩版：将 $s$ 中每个极长连续相同字符段替换为单个该字符。

例如 $f(\text{"aabbcc"}) = \text{"abc"}$。

定义 $|s|$ 为字符串 $s$ 的长度，$|f(s)|$ 即为压缩后的长度。

例如 $|f(\text{"aabbcc"})| = |\text{"abc"}| = 3$。

空串的长度为 $0$。

给定一个长度为 $n$ 的字符串 $s$，由小写字母组成。

你必须恰好删除一个字符 $s[i]$（$2 \le i \le n-1$，首尾不可删），得到新字符串 $s'$。

求 $|f(s')|$ 的最小可能值。

输入格式

第一行一个整数 $t$（$1 \le t \le 10^{4}$），表示测试数据组数。

每组测试数据：

• 第一行一个整数 $n$（$3 \le n \le 2 \times 10^{5}$），表示字符串长度。

• 第二行一个字符串 $s$（$|s| = n$），由小写字母组成。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^{5}$。

输出格式

对于每组测试数据，输出一行一个整数，表示删除一个字符后压缩字符串的最小可能长度。

样例

9
3
abb
3
aab
3
abc
4
abaa
4
abba
5
eeeee
6
yyssee
7
abacaba
18
goodluckandhavefun

2
2
2
1
3
1
3
5
16

样例解释

• 第一组：只能删除 $s[2] =$ 'b'，$s' =$ "ab"，$|f(s')| = 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$。

数据范围

• $1 \le t \le 10^{4}$

• $3 \le n \le 2 \times 10^{5}$

• $\sum n \le 2 \times 10^{5}$