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.

Samples

4
4
abcd
4
abbc
4
abba
6
abbccc

4
4
3
4