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 $ .

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.

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.