Minimum Toggles for Uniform Bulbs

You are given T test cases. In each test case, you are given an integer N representing the number of bulbs and a string S of length N, where each character is either 0 (off) or 1 (on). Your task is to determine the minimum number of toggles required to make all bulbs uniform (i.e. all on or all off).

A single toggle operation can flip a contiguous block of bulbs. An optimal strategy is achieved by counting the number of transitions between 0 and 1 in the string. Let the number of such transitions be transitions. The minimum toggles required is then given by the formula:

\( \left\lceil \frac{\text{transitions}}{2} \right\rceil \)

For example, for the string 001100, there is 1 toggle needed while for 1010 there are 2 toggles required.

inputFormat

The first line contains a single integer T indicating the number of test cases. For each test case, the first line contains an integer N (the number of bulbs). The next line contains a binary string S of length N indicating the state of each bulb.

outputFormat

For each test case, output a single line containing the minimum number of toggles required to make all bulbs uniform.

## sample

3
6
001100
4
1010
5
11111

1
2
0

</p>