CF2192A.String Rotation Game

Define a block in a string as a contiguous substring of characters of the same type that cannot be extended either to the left or the right. For example, in the string aabcccdaa, there are five blocks:

• aa ($1$-st to $2$-nd characters)
• b ($3$-rd character)
• ccc ($4$-th to $6$-th characters)
• d ($7$-th character)
• aa ($8$-th to $9$-th characters).

You are playing a game where you are given a string $s$ of length $n$. You can cyclically rotate$^{\text{∗}}$ the string however you want. Your score is then calculated as the number of blocks in the final string. Please find the maximum score possible.

$^{\text{∗}}$Formally, choose an index $1 \leq i \leq n$, and replace the string $s_1s_2\ldots s_n$ with the string $s_{i+1}s_{i+2}\ldots s_ns_1s_2\ldots s_{i}$. For example, the string abcde can be rotated to string deabc by choosing $i=3$.

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

• aa（第 $1$ 至 $2$ 个字符）
• b（第 $3$ 个字符）
• 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 可通过选取 $i=3$ 移位为 deabc。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$).

The second line of each test case contains the string $s$ of length $n$.

Strings $s$ consist of lowercase Latin characters only.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是测试用例的描述。

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

每个测试用例的第二行包含长度为 $n$ 的字符串 $s$。

字符串 $s$ 仅由小写拉丁字母组成。

For each testcase, output a single integer denoting the maximum score you can achieve.

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

In the first test case, score of the original string abcd is $4$. It can be shown that a score greater than $4$ cannot be achieved.

In the second test case, cyclically rotating the string by $2$ positions will give us string bcab. Score of this string is $4$. It can be shown that a score greater than $4$ cannot be achieved.

在第一个测试用例中，原字符串 abcd 的得分为 $4$。可以证明无法得到大于 $4$ 的得分。

在第二个测试用例中，将字符串循环右移 $2$ 位可得到字符串 bcab，其得分为 $4$。可以证明无法得到大于 $4$ 的得分。