A binary string is a string consisting only of the characters 0 and 1. You are given a binary string $s_1 s_2 \ldots s_n$. It is necessary to make this string non-decreasing in the least number of operations. In other words, each character should be not less than the previous. In one operation, you can do the following:

Select an arbitrary index $1 \leq i \leq n$ in the string;

For all $j \geq i$, change the value in the $j$-th position to the opposite, that is, if $s_j = 1$, then make $s_j = 0$, and vice versa.

What is the minimum number of operations needed to make the string non-decreasing?


-----Input-----

Each test consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test cases a single integer $n$ ($1 \leq n \leq 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 \cdot 10^5$.


-----Output-----

For each test case, output a single integer — the minimum number of operations that are needed to make the string non-decreasing.


-----Examples-----

Input
8
1
1
2
10
3
101
4
1100
5
11001
6
100010
10
0000110000
7
0101010
Output
0
1
2
1
2
3
1
5


-----Note-----

In the first test case, the string is already non-decreasing.

In the second test case, you can select $i = 1$ and then $s = \mathtt{01}$.

In the third test case, you can select $i = 1$ and get $s = \mathtt{010}$, and then select $i = 2$. As a result, we get $s = \mathtt{001}$, that is, a non-decreasing string.

In the sixth test case, you can select $i = 5$ at the first iteration and get $s = \mathtt{100001}$. Then choose $i = 2$, then $s = \mathtt{111110}$. Then we select $i = 1$, getting the non-decreasing string $s = \mathtt{000001}$.

Difficulty: EASY
Tags: Dynamic programming

Complete search

Implementation

Greedy algorithms
Skill types: Dynamic programming

Complete search

Greedy algorithms

Starter code:

Solutions:
for s in [*open(0)][2::2]:
	s = s.strip()
	k = sum((a != b for (a, b) in zip(s, s[1:])))
	print(max(k - 1, 0) + ('0' in s and s[0] == '1'))


import sys
input = sys.stdin.readline
from math import ceil, comb
list_input = lambda x=int: list(map(x, input().strip().split()))
mult_input = lambda x=int: map(x, input().strip().split())

def solve():
	n = int(input())
	s = input().rstrip('\n')
	l = list(s)
	ans = 0
	(o, z) = (0, 0)
	for (i, x) in enumerate(l):
		if x == '0':
			if o:
				if l[i - 1] == '0':
					continue
				ans += 1
			z = 1
		else:
			if z and o:
				if l[i - 1] == '1':
					continue
				ans += 1
			o = 1
	return ans
for _ in range(int(input())):
	print(solve())


n = int(input())
datas = []
for i in range(n):
	l = input()
	t = str(input())
	datas.append(t)

def solve(data):
	if not data:
		return 0
	r = 0
	last = data[0]
	for i in data[1:]:
		if i != last:
			r += 1
		last = i
	if data[0] == '0':
		r -= 1
	return max(r, 0)
for d in datas:
	print(solve(d))


def main():

	def main():
		T = readInt()
		for _ in range(T):
			N = readInt()
			A = readString()
			print(solve(A, N))

	def solve(A, N):
		A = A.lstrip('0')
		if not A:
			return 0
		p = A[0]
		ans = 0
		for x in A:
			if x != p:
				ans += 1
				p = x
		return ans
	main()
MOD = 10 ** 9 + 7
import sys
from math import ceil
from itertools import groupby
from collections import deque, Counter, defaultdict
from bisect import bisect_left, bisect_right, insort
from pprint import pprint
read = sys.stdin.readline
readString = lambda : read().strip()
readInt = lambda : int(readString())
readStrings = lambda delim=' ': readString().split(delim)
readInts = lambda delim=' ': [int(_) for _ in readStrings(delim)]
main()


import sys
import math

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	s = list(inp())
	for i in range(n):
		if s[i] == '1':
			ans = 0
			for i in range(i + 1, n):
				ans += s[i] != s[i - 1]
			print(ans)
			return
	print(0)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	c = 0
	x = '0'
	for i in s:
		if i == '0':
			if x == '0':
				continue
			elif c % 2 == 0:
				c += 1
		elif x == '0':
			x = '1'
			continue
		elif c & 1:
			c += 1
	print(c)


import sys
c = 0
n = 0
for line in sys.stdin:
	if c == 0:
		n = 2 * int(line)
	elif c % 2 == 0:
		s = line
		i = 0
		one = False
		if s[0] == '1':
			one = True
		trans = 0
		for i in range(1, len(s) - 1):
			if s[i] != s[i - 1]:
				trans += 1
		if trans == 0:
			print(0)
			c += 1
			continue
		elif one:
			print(trans)
		else:
			print(trans - 1)
	c += 1
	if n < c:
		break


def fuc(s):
	for i in range(len(s)):
		if s[i] == '1':
			s = s[i:]
			break
	res = 0
	for i in range(len(s) - 2, -1, -1):
		if s[i] != s[i + 1]:
			res += 1
	return res
n = int(input())
res = []
for _ in range(n):
	i = input()
	s = input()
	res.append(fuc(s))
for re in res:
	print(re)


t = int(input())
ans = [0] * t
for i in range(t):
	n = int(input())
	s = input()
	g = 1
	for j in range(1, n):
		if s[j - 1] != s[j]:
			g += 1
	ans[i] = g - 1 if s[0] == '1' else g - 2
	if g == 1:
		ans[i] = 0
for a in ans:
	print(a)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	if '1' not in s:
		print(0)
	elif '0' not in s:
		print(0)
	else:
		i = s.index('1')
		count = 0
		for k in range(i, n - 1):
			if s[k] != s[k + 1]:
				count += 1
		print(count)


import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
input = sys.stdin.readline
T = int(input())
res = []
for _ in range(T):
	N = int(input())
	s = input().strip()
	(i, ans) = (0, 0)
	while s[i] == '0' and i < N - 1:
		i += 1
	for j in range(i, N - 1):
		if s[j] != s[j + 1]:
			ans += 1
	res.append(ans)
print(*res, sep='\n')


import sys
import math
ZERO = '0'
ONE = '1'
NA = '*'
num_of_cases = int(sys.stdin.readline().rstrip())
for _ in range(num_of_cases):
	ans = 0
	array_len = int(sys.stdin.readline().rstrip())
	arr = sys.stdin.readline().rstrip()
	curr = NA
	for e in arr:
		if curr == NA:
			if e == ONE:
				curr = e
		elif curr == e:
			continue
		else:
			ans += 1
			curr = e
	print(ans)


for _ in range(int(input())):
	(n, s) = (int(input()), input())
	print(max((s[0] == '1') + sum((s[i] != s[i - 1] for i in range(1, n))) - 1, 0))


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	if n == 1:
		print(0)
	else:
		count = 0
		first = s[0]
		for ch in s[1:]:
			if first != ch:
				first = ch
				count += 1
		if count == 1 and s[0] == '0':
			count = 0
		elif count > 1:
			if s[0] == '0':
				count -= 1
		print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if s.count('1') == n or s.count('0') == n:
		print(0)
		continue
	s = s[s.index('1'):]
	print(s.count('01') + s.count('10'))


import math
import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	S = readStr()
	cnt = 0
	idx = -1
	for i in range(1, n):
		if S[i - 1] == '1' and S[i] == '0':
			idx = i
		if idx > -1 and S[i] != S[i - 1]:
			cnt += 1
	return cnt
for _ in range(int(input())):
	print(solve())


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	start = s[0]
	count = 0
	for i in s:
		if i != start:
			count += 1
			start = i
	if s[0] == '0':
		print(max(0, count - 1))
	else:
		print(count)


def print_val(length, comb):
	comparer = '1'
	count = 0
	for i in range(length):
		if comb[i] == comparer:
			count += 1
			if comparer == '0':
				comparer = '1'
			else:
				comparer = '0'
	if count == 0:
		print(0)
	else:
		print(count - 1)

def main():
	n = int(input())
	for i in range(n):
		length = int(input())
		comb = input().rstrip()
		print_val(length, comb)
main()


testCase = int(input())
for i in range(testCase):
	n = int(input())
	binary = input()
	count = 0
	for i in range(n - 1):
		if binary[i] != binary[i + 1]:
			count += 1
	if binary[0] == '0':
		ans = max(count - 1, 0)
	else:
		ans = count
	print(ans)


def main():
	n = int(input())
	s = input()
	count = 0
	i = n - 1
	prev0 = False
	prev1 = False
	while i > -1:
		if s[i] == '0':
			prev0 = True
			while i > -1 and s[i] == '0':
				i -= 1
			continue
		if prev0:
			count += 2 if prev1 else 1
			prev0 = False
		prev1 = True
		i -= 1
	print(count)
for _ in range(int(input())):
	main()


def test_case():
	_ = int(input())
	s = input()
	chunks = []
	prev = s[0]
	for v in s[1:]:
		if v != prev:
			chunks.append(prev)
			prev = v
	chunks.append(prev)
	if len(chunks) == 1:
		print(0)
	else:
		print(len(chunks) - 1 - (1 if chunks[0] == '0' else 0))
test_cases = int(input())
for _ in range(test_cases):
	test_case()


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		ans = 0
		ind = 0
		while s[ind] == 0 and ind < n:
			ind += 1
		actual = s[ind]
		if ind == 0 and s[ind] == '1':
			ans += 1
		for i in range(ind, n):
			if s[i] != actual:
				ans += 1
				actual = s[i]
		print(max(ans - 1, 0))
main()


def ii(a=False):
	i = input().split()
	try:
		if len(i) == 1 and (not a):
			return int(i[0])
		return list(map(int, i))
	except Exception:
		if len(i) == 1 and (not a):
			return i[0]
		return i

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(ii()):
	n = ii()
	s = input()
	index = 0
	for i in range(n):
		if s[i] != '0':
			index = i
			break
	t = 0
	s = s[index:]
	prev = s[0]
	for i in s:
		if prev != i:
			t += 1
			prev = i
	print(t)


import sys
input = sys.stdin.readline

def inverse(el, inv):
	if inv:
		return not el
	return el
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip()))
	cnt = 0
	is_one = False
	inv = False
	for i in range(n):
		if not is_one and a[i] == 0:
			continue
		if inverse(a[i], inv) == 1:
			is_one = True
		elif is_one:
			inv = not inv
			cnt += 1
	print(cnt)


def solve():
	n = int(input())
	s = input()
	ret = 0
	f = True
	for i in range(1, n):
		if f and s[i] == '0' and (s[i - 1] == '1'):
			f = False
			ret += 1
		elif not f and s[i] == '1' and (s[i - 1] == '0'):
			f = True
			ret += 1
	print(ret)
for _ in range(int(input())):
	solve()


def min_operations(s, n):
	counter_change = 0
	flag_change = -1
	for i in range(0, n - 1):
		if flag_change == 1:
			if s[i + 1] > s[i]:
				counter_change += 1
				flag_change *= -1
		if flag_change == -1:
			if s[i + 1] < s[i]:
				counter_change += 1
				flag_change *= -1
	return counter_change
test_number = int(input())
for test in range(test_number):
	n = int(input())
	s = input()
	print(min_operations(s, n))


import math

def solve():
	n = int(input())
	str = input()
	cur = '0'
	c = 0
	for i in range(n):
		if str[i] != cur:
			c += 1
			cur = str[i]
	print(max(0, c - 1))
t = int(input())
while t:
	solve()
	t = t - 1


for _ in range(int(input())):
	x = input()
	bina = input()
	f = '0'
	c = -1
	for i in bina:
		if i != f:
			c += 1
			f = '0' if f == '1' else '1'
	if c == -1:
		c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	if '1' not in s:
		print(0)
	elif '0' not in s:
		print(0)
	else:
		i = s.index('1')
		count = 0
		for k in range(i, n - 1):
			if s[k] != s[k + 1]:
				count += 1
		print(count)


test_n = int(input())
for _ in range(test_n):
	size = input()
	string = input().lstrip('0')
	flips = 0
	last = '1'
	flipped = False
	for b in string:
		if not flipped:
			if last > b:
				flips += 1
				flipped = not flipped
		elif last < b:
			flips += 1
			flipped = not flipped
		last = b
	print(f'{flips}')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if s[0] == '0' and s.count('1') > 0:
		a = s.count('10') + s.count('01')
		print(a - 1)
	else:
		a = s.count('10') + s.count('01')
		print(a)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	cnt = 0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			cnt += 1
	if s[0] == '0':
		cnt = max(0, cnt - 1)
	print(cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s_rev = s[::-1]
	problem_index = -1
	for i in range(n - 1):
		if s_rev[i] == '0' and s_rev[i] != s_rev[i + 1]:
			problem_index = n - i - 2
			break
	if problem_index == -1:
		print(0)
	else:
		ans = 1
		for i in range(problem_index):
			if s[i] == '1' and s[i] != s[i + 1]:
				ans += 2
		if s[-1] == '1':
			ans += 1
		print(ans)


import sys
from collections import defaultdict
import heapq
input = sys.stdin.readline

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
while t > 0:
	n = int(input())
	s = input()
	ans = 0
	flip = 0
	for i in range(1, n):
		if flip == 0 and s[i] == '0' and (s[i - 1] == '1'):
			flip = 1
			ans += 1
		elif flip == 1 and s[i] == '1' and (s[i - 1] == '0'):
			flip = 0
			ans += 1
	print(ans)
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	s = str(input())
	f = 0
	ans = 0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			if f == 0 and s[i] == '0':
				f = 1
				ans += 1
			elif f == 1:
				ans += 1
	print(ans)
	t = t - 1


for _ in range(int(input())):
	n = input()
	st = input()
	(s, o, z) = (0, False, False)
	for el in st[::-1]:
		if el == '1':
			if z and o:
				s += 2
			elif z:
				s += 1
			z = False
			o = True
		else:
			z = True
	print(s)


import math
import bisect
from collections import Counter
for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	if s[0] == '0' and s.count('1') > 0:
		c = s.count('01') + s.count('10')
		print(c - 1)
	else:
		c = s.count('01') + s.count('10')
		print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().lstrip('0')
	i = '1'
	c = 0
	for b in s:
		if b != i:
			i = b
			c += 1
	print(c)


testcases = int(input())
for _ in range(testcases):
	n = int(input())
	s = input().strip()
	counter = 0
	for (c1, c2) in zip(s[:-1], s[1:]):
		if c1 != c2:
			counter += 1
	if s[0] == '1':
		counter += 1
	if len(set(s)) == 1:
		print(0)
	else:
		print(counter - 1)


def solve():
	n = int(input())
	s = input()
	m = [s[0]]
	for i in range(1, n):
		if s[i] != m[-1]:
			m.append(s[i])
	if len(m) == 1:
		print(0)
		return
	if s[0] == '0':
		print(len(m) - 2)
	else:
		print(len(m) - 1)
t = int(input())
for _ in range(t):
	solve()


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	s = input()
	count = 0
	(zero, one) = (s.count('0'), s.count('1'))
	if zero == 0 or one == 0:
		print(0)
		return
	net = 0
	for i in s:
		if net % 2 == 0:
			c = i
		elif i == '0':
			c = '1'
		else:
			c = '0'
		if c == '1':
			net += 1
	print(net - 1)
t = int(input())
while t != 0:
	solve()
	t -= 1


def exe():
	if '1' not in s:
		return 0
	ind = s.index('1')
	ans = 0
	for i in range(ind, n - 1):
		if s[i] != s[i + 1]:
			ans += 1
	return ans
for i in range(int(input())):
	n = int(input())
	s = list(input())
	print(exe())


def check():
	for i in range(n):
		if s[i] == '1':
			return True
	else:
		return False
for i in range(int(input())):
	n = int(input())
	s = list(input())
	if not check():
		print(0)
		continue
	ind = s.index('1')
	l = [i for i in range(ind, n - 1) if s[i] != s[i + 1]]
	print(len(l))


import math
t = int(input())

def solve():
	n = int(input())
	s = input()
	ans = 0
	if s[-1] == '0' and s.count('0') != n:
		ans += 1
	i = 0
	cnt = 0
	while i < n:
		if s[i] == '1':
			i += 1
			while i < n and s[i] == '1':
				i += 1
			if i == n:
				print(ans)
				return
			while i < n and s[i] == '0':
				i += 1
			if i != n:
				ans += 2
		else:
			i += 1
	print(ans)
while t:
	solve()
	t -= 1


def solve(s):
	f = 0
	ans = 0
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			if f == 0 and s[i] == '0':
				f = 1
				ans += 1
			elif f == 1:
				ans += 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(solve(s))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	L = '2'
	k = 0
	for i in s:
		if i == '1' and L == '2':
			L = '1'
		elif L != '2' and i != L:
			k += 1
			L = i
	print(k)


case = int(input())
for i in range(case):
	n = int(input())
	ss = input()
	kk = list(ss)
	tt = kk.copy()
	tt.sort()
	if kk == tt:
		print(0)
		continue
	ss += '333'
	one = ss.index('1')
	if '1' in ss:
		print(ss[one:].count('10') + ss[one:].count('01'))


for _ in range(int(input())):
	n = int(input())
	s = input()
	(l, r) = (s.find('1'), s.rfind('1'))
	if list(s) == sorted(s):
		print(0)
	else:
		ans = 0 if r == n - 1 else 1
		for i in range(l, r):
			if s[i] != s[i + 1]:
				ans += 1
		print(ans)


t = int(input())
for num in range(0, t):
	g = int(input())
	a = input()
	o = 1
	v = '1'
	ans = 0
	u = 0
	for num in a:
		if u == 0:
			if num == '1':
				u = 1
		elif num != v:
			ans = ans + 1
			v = num
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = input()
	if '1' in l:
		t = l.index('1')
	else:
		t = l.index('0')
	y = l[t:]
	char = y[0]
	c = 0
	for j in range(len(y)):
		if y[j] == char:
			continue
		else:
			c += 1
			char = y[j]
	print(c)


import math

def primeFactors(n):
	l = []
	c = 2
	while n > 1:
		if n % c == 0:
			l.append(c)
			n = n / c
		else:
			c = c + 1
	return l
import math

def primeFactors(n):
	l = []
	c = 2
	while n > 1:
		if n % c == 0:
			l.append(c)
			n = n / c
		else:
			c = c + 1
	return l

def prime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
	return prime_flag
t = int(input())
while t:
	n = int(input())
	s = input()
	pos = -1
	if n == 1:
		print(0)
	else:
		for i in range(n):
			if s[i] == '1':
				pos = i
				break
		if pos == -1:
			print(0)
		elif pos == n - 1:
			print(0)
		else:
			cnt = 0
			ones = True
			zeroes = False
			for i in range(pos + 1, n):
				if s[i] == '0':
					if not zeroes:
						cnt += 1
						zeroes = True
						ones = False
				elif not ones:
					cnt += 1
					ones = True
					zeroes = False
			print(cnt)
	t = t - 1


import math
t = int(input())

def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)

def allgcd(arr):
	gc = arr[0]
	for i in range(1, len(arr)):
		gc = gcd(gc, arr[i])
	return gc
for tc in range(1, t + 1):
	n = int(input())
	s = list(input())
	ops = 0
	oneseen = False
	for i in range(len(s)):
		if ops % 2 == 0:
			ch = s[i]
		else:
			ch = '0' if s[i] == '1' else '1'
		if ch == '1':
			oneseen = True
		elif oneseen:
			ops += 1
			oneseen = True
		else:
			continue
	print(ops)


for _ in range(int(input())):
	n = int(input())
	s = input()
	s2 = ''
	for c in s:
		if s2 and s2[-1] != c:
			s2 += c
		elif not s2:
			s2 += c
	if len(s2) == 1:
		print(0)
	elif s2[0] == '0':
		print(len(s2) - 2)
	else:
		print(len(s2) - 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = 0
	for pos in range(1, n):
		if s[pos] != s[pos - 1]:
			cnt += 1
	if s[0] == '0':
		cnt = max(0, cnt - 1)
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	s = input()
	prev = s[0]
	order = 1
	dec = 0
	inc = 0
	for i in range(1, n):
		if order:
			if prev == '1' and s[i] == '0':
				order = 0
				dec += 1
		elif prev == '0' and s[i] == '1':
			order = 1
			inc += 1
		prev = s[i]
	print(inc + dec)


for _ in range(int(input())):
	n = int(input())
	string = str(input())
	k = 0
	p = 0
	while p < n and string[p] == '0':
		p += 1
	for i in range(p, n):
		if string[i] == '1':
			if i + 1 < n and string[i + 1] == '0':
				k += 1
		elif i + 1 < n and string[i + 1] == '1':
			k += 1
	print(k)


def exe():
	for i in range(n):
		if s[i] == '1':
			break
	else:
		return '0'
	for i in range(n):
		if s[i] == '1':
			ind = i
			break
	ans = 0
	for i in range(ind, n - 1):
		if s[i] != s[i + 1]:
			ans += 1
	return ans
for i in range(int(input())):
	n = int(input())
	s = list(input())
	print(exe())


for _ in range(int(input())):
	x = int(input())
	l = input()
	for i in range(x):
		if l[i] == '1':
			break
	las = '1'
	c = 0
	for i in range(i + 1, x):
		if l[i] != las:
			c += 1
			las = l[i]
	print(c)


def solve():
	n = int(input())
	s = input()
	s = list(s)
	pos = -1
	for i in range(0, n):
		if s[i] == '1':
			pos = i
			break
	if pos == -1:
		print(0)
	else:
		tot = 0
		for i in range(pos + 1, n):
			if tot % 2 == 1:
				if s[i] == '1':
					s[i] = '0'
				else:
					s[i] = '1'
			if s[i] == '0':
				tot += 1
		print(tot)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			count = count + 1
	if count > 0:
		if s[0] == '1':
			print(count)
		else:
			print(count - 1)
	else:
		print(0)


import math
for _ in range(int(input())):
	n = int(input())
	l = input()
	res = 0
	for j in range(n - 1):
		if l[j] == l[j + 1]:
			continue
		else:
			res += 1
	if res > 0 and l[0] == '0':
		res -= 1
	print(res)


n = int(input())
for i in range(n):
	input()
	s = input()
	m = s[0]
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			m += s[i]
	if s[0] == '0':
		if len(m) == 1:
			print(0)
		else:
			print(len(m) - 2)
	else:
		print(len(m) - 1)


def ugu(s):
	ans = 0
	flag = False
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			if not flag and s[i] == '0':
				ans += 1
				flag = True
			elif flag:
				ans += 1
	return ans
n = int(input())
for _ in range(n):
	k = int(input())
	s = input()
	print(ugu(s))


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	(bi, ei) = (-1, n)
	while bi < n - 1 and s[bi + 1] == '0':
		bi += 1
	count = 0
	for i in range(n - 1, bi, -1):
		if i - 1 > bi and s[i] != s[i - 1]:
			count += 1
	print(count)


t = int(input())
while t != 0:
	n = int(input())
	s = input()
	res = ''
	res += s[0]
	for i in range(1, n):
		if s[i] != s[i - 1]:
			res += s[i]
	if res == '0' or res == '1' or res == '01':
		print(0)
	elif res[0] == '1' and res[len(res) - 1] == '1':
		print(len(res) - 1)
	elif res[0] == '1' and res[len(res) - 1] == '0':
		print(len(res) - 1)
	elif res[0] == '0' and res[len(res) - 1] == '0':
		print(len(res) - 2)
	else:
		print(len(res) - 2)
	t -= 1


n = int(input())
inpt = []
for i in range(n):
	inpt.append((int(input()), input()))
for i in inpt:
	string = i[1]
	length = i[0]
	ones = string.count('1')
	zeros = length - ones
	checking = True
	pointer = 0
	moves = 0
	zero = '0'
	one = '1'
	while pointer < length:
		if checking:
			para = zero
		else:
			para = one
		if string[pointer] == para:
			pointer += 1
			zeros -= 1
			if zeros == 0 or ones == 0:
				break
		elif zeros == 0:
			break
		else:
			checking = not checking
			ones -= 1
			(ones, zeros) = (zeros, ones)
			pointer += 1
			moves += 1
			continue
	print(moves)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	ans = 0
	i = 1
	while i < n:
		if s[i - 1] > s[i]:
			k = s[i - 1]
			while 1:
				if i == n:
					break
				else:
					if k != s[i]:
						ans += 1
						k = s[i]
					i += 1
		i += 1
	print(ans)


t = int(input())
for xyz in range(t):
	n = int(input())
	l = input()
	if n == 1:
		print(0)
	else:
		i = 0
		while l[i] == '0':
			if i == n - 1:
				break
			i += 1
		change = 0
		current = l[i]
		while i < n:
			if l[i] != current:
				change += 1
				current = l[i]
			i += 1
		print(change)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	i = 0
	while i < n and s[i] == '0':
		i += 1
	count = 0
	while i < n - 1:
		if s[i] != s[i + 1]:
			count += 1
		i += 1
	print(count)


t = int(input())
for x in range(t):
	n = int(input())
	s = str(input())
	counter = 0
	index = 0
	for i in range(n):
		if s[i] == '0':
			continue
		else:
			index = i
			break
	for i in range(index, n - 1):
		if s[i] == s[i + 1]:
			continue
		else:
			counter += 1
	print(counter)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	count = 0
	fo = 0
	for i in range(len(s)):
		if s[i] == '1':
			fo = i
			break
	for i in range(fo, len(s) - 1):
		if s[i] != s[i + 1]:
			count += 1
	print(count)


for t in range(int(input())):
	n = int(input())
	s = input()
	result = 0
	vis = False
	count = 0
	for i in s:
		if i == '1' and count % 2 == 0:
			vis = True
			continue
		if vis and (i == '0' and count % 2 == 0 or (i == '1' and count % 2 == 1)):
			result += 1
			count += 1
			continue
	print(result)


for _ in range(int(input())):
	n = int(input())
	arr = [el for el in input()]
	ans = 0
	i = 0
	while i < n and arr[i] == '0':
		i += 1
	start = i
	for i in range(start + 1, n):
		if arr[i] == arr[i - 1]:
			pass
		else:
			ans += 1
	print(ans)


for _ in range(int(input())):
	length = int(input())
	myList = [int(i) for i in input().lstrip('0').lstrip('1')]
	sample = counter = 0
	for i in myList:
		if i == sample:
			counter += 1
			sample = 1 - sample
	print(counter)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	count = 1
	idx = 0
	while idx < n and s[idx] == '0':
		idx += 1
	idx += 1
	while idx < n:
		if s[idx] != s[idx - 1]:
			count += 1
		idx += 1
	print(max(0, count - 1))


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	res = s[0]
	x = s[0]
	for i in range(1, len(s)):
		if s[i] == x:
			continue
		else:
			res += s[i - 1]
			x = s[i]
	if len(res) == 1:
		print(0)
	elif res.startswith('0'):
		print(len(res) - 2)
	else:
		print(len(res) - 1)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	i = 0
	while i < n and s[i] == '0':
		i += 1
	while i < n and s[i] == '1':
		i += 1
	flipped = 0
	ans = 0
	for j in range(i, n):
		if flipped == 1 and s[j] == '1' or (flipped == 0 and s[j] == '0'):
			ans += 1
			flipped = flipped ^ 1
	print(ans)


from math import *
for _ in range(int(input())):
	n = int(input())
	str = input()
	t = str[0]
	for val in str:
		if val == '0' and t == '1':
			t = '1234567'
			break
		else:
			t = val
	if t != '1234567':
		print(0)
	else:
		i = 0
		while str[i] == '0':
			i += 1
		sm = 0
		while i < n:
			if str[i] == '1' and sm % 2 == 1:
				sm += 1
			elif str[i] == '0' and sm % 2 == 0:
				sm += 1
			i += 1
		print(sm)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	cnt = 0
	for j in range(n - 1):
		if s[j] != s[j + 1]:
			cnt = cnt + 1
	if s[0] == '0' and s.count('1') > 0:
		cnt = cnt - 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	while i < n and s[i] == '0':
		i += 1
	while i < n and s[i] == '1':
		i += 1
	ans = 0
	while i < n:
		if s[i - 1] != s[i]:
			ans += 1
		i += 1
	print(ans)


def helper(s):
	h = {'1': 1, '0': 0}
	ans = 0
	c = 0
	opp = {'1': '0', '0': '1'}
	for i in range(len(s)):
		if h[s[i]] == 1:
			c += 1
		if h[s[i]] == 0 and c > 0:
			ans += 1
			h[s[i]] = 1
			h[opp[s[i]]] = 0
			c = 1
	return ans
for i in range(int(input())):
	n = int(input())
	print(helper(input()))


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input()))
	k = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			k += 1
	if not s[0] and k:
		k -= 1
	print(k)


import math
for _ in range(int(input())):
	n = int(input())
	string = input()
	a = list(string.strip())
	if n == 1:
		print(0)
	else:
		flips = 0
		for i in range(1, n):
			if a[i - 1] != a[i]:
				flips += 1
		if a[0] == '1':
			print(flips)
		elif flips == 0:
			print(0)
		else:
			print(flips - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	ops = 0
	inverted = False
	for i in range(1, len(s)):
		if not inverted and s[i - 1] == '1' and (s[i] == '0') or (inverted and s[i - 1] == '0' and (s[i] == '1')):
			ops += 1
			inverted = not inverted
	print(ops)


N = int(input())
operations_array = [0] * N
for i in range(N):
	m = int(input())
	s = [int(x) for x in input()]
	operations = 0
	if m > 1:
		j = 0
		d = -1
		for j in range(1, m):
			if s[j] - s[j - 1] == d:
				d = -1 * d
				operations += 1
		operations_array[i] = operations
	else:
		operations_array[i] = 0
for op in operations_array:
	print(op)


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(n):
		if s[i] == '1':
			ans = 0
			for i in range(i + 1, n):
				ans += s[i] != s[i - 1]
			print(ans)
			c += 1
			break
	if c == 0:
		print(0)