题目描述

设 $f(s)$ 为字符串 $s$ 的压缩版本，其构造方式是将每段由相同字符组成的极大连续块替换为该字符的单个副本。例如，$f(\text{"aabbcc"}) = \text{"abc"}$。

令 $|s|$ 表示字符串 $s$ 的长度。相应地，$|f(s)|$ 表示压缩后字符串的长度。例如：

（如果字符串为空，则其长度为 $0$）。

给定一个由 $n$ 个小写英文字母组成的字符串 $s$。你必须恰好删除一个字符 $s_i$（其中 $2 \le i \le n-1$）来形成一个新的字符串 $s'$，请计算出 $|f(s')|$ 的最小可能值。

注意：你不能删除第一个字符 $s_1$ 或最后一个字符 $s_n$。

输入格式

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

对于每个测试用例：

• 第一行包含一个整数 $n$（$3 \le n \le 2 \times 10^5$）—— 字符串的长度。
• 第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写英文字母组成。

输出格式

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

样例输入 1

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

样例输出 1

2
2
2
1
3
1
3
5
16

说明

样例解释

• 在第一个测试用例中，我们只能删除第 $2$ 个字符 $s_2 = \text{'b'}$，得到新字符串 $s' = \text{"ab"}$，此时 $|f(s')| = 2$。因此能达到的最小长度为 $2$。
• 在第四个测试用例中，我们可以删除第 $2$ 个字符 $s_2 = \text{'b'}$。得到的新字符串为 $s' = \text{"aaa"}$，其压缩后为 $f(s') = \text{"a"}$，所以 $|f(s')| = 1$。
• 在第六个测试用例中，无论删除哪一个合法的字符，都会得到 $f(s') = \text{"e"}$，且 $|f(s')| = 1$。
• 在第八个测试用例中，我们可以删除第 $4$ 个字符 $s_4 = \text{'c'}$。得到的新字符串为 $s' = \text{"abaaba"}$，其压缩后为 $f(s') = \text{"ababa"}$，长度为 $|f(s')| = 5$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $3 \le n \le 2 \times 10^5$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
• 保证给定的字符串仅由小写英文字母组成。