You have decided to visit your friend from Ozersk. However, at the entrance to the city, you were stopped and asked to solve a problem to make sure that you can actually drive into the territory of the closed city.
A binary string is a string consisting only of the characters 0 and 1. The police officer gave you the binary string s
1s
2 ... s
n. You need to sort this string (that is, turn it into a string like 00 ... 0011 ... 11) in the least number of operations. In one operation, you can do the following:
x Pick an arbitrary index in row 1 <= i <= n;
x For all j >= i, change the value in the jth position to the opposite, that is, if s
j = 1, then make s
j = 0, and vice versa.
Input
Each test consists of several sets of input data. The first line contains an integer t (1 <= t <= 10
4) the number of test cases. The following is a description of the input datasets.
The first line of each test case contains a single integer n (1 <= n <= 10
5) the length of the string.
The second line of each test case contains a binary string s of length n.
It is guaranteed that the sum of n over all test cases does not exceed 2 ·10
5.
Imprint
For each test case, print a single integer, the minimum number of operations that need to be done to sort the string.
Examples
| # |
Input |
Output |
| 1 |
6
1
1
2
10
3
101
4
1100
5
11001
6
100010 |
0
1
2
1
2
3 |
Remark
In the first test case, the string is already sorted.
In the second test case, you can choose i = 1 and then s = 01.
In the third test case, you can choose i = 1 and get s = 010, and then choose i = 2. As a result, we get s = 001, that is, a sorted string.
In the sixth test case, you can choose i = 5 at the first iteration and get s = 100001. Then choose i = 2, then s = 111110. Then choose i = 1, getting the
tagged string s = 000001.