← 返回题目列表

Codeforces · 2192/A

A. 弦轮旋转游戏

中文机器翻译题面 查看原题

定义一个 块 在字符串中作为相同类型的字符的连续子字符串,不能向左或向右扩展。例如,在字符串中 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$$$ 仅包含小写拉丁字符。

输出

对于每个测试用例,输出一个整数,表示您可以获得的最高分数。

示例

输入
复制

4
4
abcd
4
abbc
4
abba
6
abbccc

输出
复制

4
4
3
4

注意

在第一个测试用例中,原始字符串的分数 abcd 是 $$$4$$$。可以看出,无法获得大于 $$$4$$$ 的分数。

在第二个测试用例中,将字符串循环旋转 $$$2$$$ 位置将得到字符串 BCAB。该字符串的分数为$$$4$$$。可以看出,无法获得大于 $$$4$$$ 的分数。