题目描述

定义一个字符串中的“块”为一个由相同字符类型组成的连续子串，并且该子串无法向左或向右扩展。例如，在字符串 aabcccdaa 中，有五个块：

• aa（第 $1$ 到第 $2$ 个字符）
• b（第 $3$ 个字符）
• ccc（第 $4$ 到第 $6$ 个字符）
• d（第 $7$ 个字符）
• aa（第 $8$ 到第 $9$ 个字符）

你在玩一个游戏，给定一个长度为 $n$ 的字符串 $s$。你可以随意对字符串进行循环旋转*。你的得分是最终字符串中块的数量。请找出可能的最大得分。

*正式定义：选择一个索引 $1 \le i \le n$，将字符串 $s_1s_2 \dots s_n$ 改成 $s_{i+1}s_{i+2} \dots s_ns_1s_2 \dots s_i$。例如，字符串 abcde 可以通过选择 $i=3$ 旋转为 deabc。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t(1 \le t \le 500)$。

每个测试用例的第一行包含一个整数 $n(1 \le n \le 100)$。

每个测试用例的第二行包含字符串 $s$，长度为 $n$。 字符串 $s$ 仅由小写拉丁字母组成。

输出格式

对于每个测试用例，输出一个整数，表示可能的最大得分。

说明/提示

• 在第一个测试用例中，原始字符串 abcd 的得分为 $4$。可以证明无法获得大于 $4$ 的得分。
• 在第二个测试用例中，将字符串循环旋转 $2$ 个位置得到 bcab，该字符串的得分为 $4$。可以证明无法获得大于 $4$ 的得分。

样例

4
4
abcd
4
abbc
4
abba
6
abbccc

4
4
3
4