定义一个 块 在字符串中作为相同类型的字符的连续子字符串,不能向左或向右扩展。例如,在字符串中 aabccccdaa,有五个块:
- aa ($$$1$$$-st 到 $$$2$$$-nd 字符)
- b ($$$3$$$-rd 字符)
- ccc (第 $$$4$$$ 到第 $$$6$$$ 个字符)
- d (第 $$$7$$$ 个字符)
- aa (第 $$$8$$$ 到第 $$$9$$$ 个字符)。
您正在玩一个游戏,其中给您一个长度为 $$$n$$$ 的字符串 $$$s$$$。您可以根据需要循环旋转$$$^{\text{*}}$$$ 字符串。然后,您的分数将计算为最终字符串中的块数。请找出可能的最高分数。
$$$^{\text{*}}$$$形式上,选择索引 $$$1 \leq i \leq n$$$,并将字符串 $$$s_1s_2\ldots s_n$$$ 替换为字符串 $$$s_{i+1}s_{i+2}\ldots s_ns_1s_2\ldots s_{i}$$$。例如,字符串 abcde 可以旋转为字符串 deabc 通过选择$$$i=3$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$)。
每个测试用例的第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$。
字符串 $$$s$$$ 仅包含小写拉丁字符。
输出
对于每个测试用例,输出一个整数,表示您可以获得的最高分数。
示例
输入复制
44abcd4abbc4abba6abbccc
输出复制
4434
注意
在第一个测试用例中,原始字符串的分数 abcd 是 $$$4$$$。可以看出,无法获得大于 $$$4$$$ 的分数。
在第二个测试用例中,将字符串循环旋转 $$$2$$$ 位置将得到字符串 BCAB。该字符串的分数为$$$4$$$。可以看出,无法获得大于 $$$4$$$ 的分数。