Minimum Operations to Make All Characters Equal

You are given a string S of length N. In one operation, you can select any substring consisting of identical characters and delete it. The goal is to reduce the string such that all remaining characters are equal. For each test case, compute the minimum number of operations required to achieve this.

More formally, let c be the number of positions i (1 ≤ i < N) where S[i] ≠ S[i-1]. The answer is given by the formula \[ \text{ans} = \left\lfloor \frac{c+1}{2} \right\rfloor + 1, \] where the division is integer division. For example:

• For S = "abb": there is 1 change, so ans = ((1+1)//2)+1 = 2.
• For S = "aabb": there is 1 change, so ans = 2.
• For S = "ababa": there are 4 changes, so ans = ((4+1)//2)+1 = 3.

This problem tests your ability to process strings and utilize greedy strategies to minimize the number of operations.

inputFormat

The first line of input contains an integer T (the number of test cases).

For each test case, the first line contains an integer N, the length of the string, and the second line contains the string S.

Example:

5
3
abb
4
aabb
6
aaaaaa
5
ababa
4
abab

outputFormat

For each test case, output a single line containing the minimum number of operations required to make all characters equal.

Example:

2
2
1
3
3

## sample

5
3
abb
4
aabb
6
aaaaaa
5
ababa
4
abab

2
2
1
3
3

</p>