Chef has a binary string S of length N. Chef can perform the following operation on S:
Insert any character (0 or 1) at any position in S.

Find the minimum number of operations Chef needs to perform so that no two consecutive characters are same in S.

------ Input Format ------

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N — the length of the binary string S.
• The second line of each test case contains a binary string S of length N containing 0s and 1s only.

------ Output Format ------

For each test case, output on a new line the minimum number of operations Chef needs to perform so that no two consecutive characters are same in S.

------ Constraints ------

$1 ≤ T ≤ 100$
$1 ≤N ≤1000$

----- Sample Input 1 ------
3
2
11
4
0101
5
00100

----- Sample Output 1 ------
1
0
2

----- explanation 1 ------
Test case 1: We can perform the following operations: $11 \rightarrow 1\underline{0}1$.

Test case 2: We do not need to perform any operations.

Test case 3: We can perform the following operations: $00100 \rightarrow 0\underline{1}0100 \rightarrow 01010\underline{1}0$.

见题面

见题面