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

Input

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.

Output

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

Note

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.

String Rotation Game

Examples