Today, Marin is at a cosplay exhibition and is preparing for a group photoshoot!

For the group picture, the cosplayers form a horizontal line. A group picture is considered beautiful if for every contiguous segment of at least $2$ cosplayers, the number of males does not exceed the number of females (obviously).

Currently, the line has $n$ cosplayers which can be described by a binary string $s$. The $i$-th cosplayer is male if $s_i = 0$ and female if $s_i = 1$. To ensure that the line is beautiful, you can invite some additional cosplayers (possibly zero) to join the line at any position. You can't remove any cosplayer from the line.

Marin wants to know the minimum number of cosplayers you need to invite so that the group picture of all the cosplayers is beautiful. She can't do this on her own, so she's asking you for help. Can you help her?


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases.

The first line of each test case contains a positive integer $n$ ($1 \leq n \leq 100$) — the number of cosplayers in the initial line.

The second line of each test case contains a binary string $s$ of length $n$ — describing the cosplayers already in line. Each character of the string is either 0 describing a male, or 1 describing a female.

Note that there is no limit on the sum of $n$.


-----Output-----

For each test case, print the minimum number of cosplayers you need to invite so that the group picture of all the cosplayers is beautiful.


-----Examples-----

Input
9
3
000
3
001
3
010
3
011
3
100
3
101
3
110
3
111
19
1010110000100000101
Output
4
2
1
0
2
0
0
0
17


-----Note-----

In the first test case, for each pair of adjacent cosplayers, you can invite two female cosplayers to stand in between them. Then, $000 \rightarrow 0110110$.

In the third test case, you can invite one female cosplayer to stand next to the second cosplayer. Then, $010 \rightarrow 0110$.

Difficulty: EASY
Tags: Mathematics

Implementation

Constructive algorithms

Starter code:

Solutions:
from sys import stdin
input = stdin.readline

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		c = 0
		for i in range(n):
			if s[i] == '0':
				if i + 1 < n and s[i + 1] != '1':
					c += 2
				elif i + 2 < n and s[i + 2] != '1':
					c += 1
		print(c)
main()


for s in [*open(0)][2::2]:
	print(sum((2 - len(x[:2]) for x in s.split('0')[1:-1])))


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


x = int(input().strip())
for i in range(x):
	a = int(input().strip())
	n = input()
	while n.count('00') > 0 or n.count('010') > 0:
		n = n.replace('00', '0110')
		n = n.replace('010', '0110')
	print(len(n) - a)


import sys

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		n = int(sys.stdin.readline())
		s = sys.stdin.readline().rstrip()
		count = 0
		left = -1
		right = -1
		for i in range(n):
			if s[i] == '0':
				if left == -1 and right == -1:
					left = right = i
				elif left != -1 and i > right:
					left = right
					right = i
				if right - left == 1:
					count += 2
				elif right - left == 2:
					count += 1
		print(count)
main()


def solve(s):
	if s == '00':
		return 2
	else:
		(r, p, d) = (0, '1', '1')
		for i in s:
			if i == '0':
				if d == '0':
					r += 2
				elif p == '0':
					r += 1
			(p, d) = (d, i)
		return r
for i in range(int(input())):
	l = input()
	print(solve(input()))


for s in [*open(0)][2::2]:
	print(sum((2 - min(2, len(x)) for x in f'**{s}*'.split('0'))))


def solve(s):
	c = 0
	i = 0
	while i < len(s) and s[i] != '0':
		i += 1
	last_index = i
	while i < len(s):
		if s[i] == '0':
			if i - last_index == 1:
				c += 2
			elif i - last_index == 2:
				c += 1
			last_index = i
		i += 1
	return str(c)
t = int(input())
out = []
for case in range(t):
	input()
	s = input()
	out.append(solve(s))
print('\n'.join(out))


tc = int(input())
for i in range(tc):
	x = int(input())
	y = input()
	str1 = y
	str1 = str1.replace('00', '0110')
	str1 = str1.replace('00', '0110')
	str1 = str1.replace('010', '0110')
	str1 = str1.replace('010', '0110')
	print(abs(y.count('1') - str1.count('1')))


a = int(input())
for i in range(a):
	b = int(input())
	c = input()
	count = 0
	while True:
		if '00' not in c and '010' not in c:
			break
		if '00' in c:
			count += c.count('00') * 2
			c = c.replace('00', '0110')
		elif '010' in c:
			count += c.count('010')
			c = c.replace('010', '0110')
	print(count)


n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	while len(s) != 0 and s[0] == '1':
		s = s[1:]
	while len(s) != 0 and s[-1] == '1':
		s = s[:-1]
	while '111' in s:
		s = s.replace('111', '11')
	if len(s) > 1:
		print((s.count('0') - 1) * 2 - s.count('1'))
	else:
		print('0')


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	b = 0
	ct = 0
	for i in s:
		if i == '0':
			if ct:
				b += ct
			ct = 2
		elif ct:
			ct -= 1
	print(b)


for _ in range(int(input())):
	n = int(input())
	str = input()
	count = 0
	for i in range(n - 1):
		if str[i] == '0' and str[i + 1] == '0':
			count += 2
		elif str[i] == '0':
			if i < n - 2 and str[i + 2] == '0':
				count += 1
	print(count)


t = int(input())
for x in range(t):
	n = int(input())
	s = input()
	if '1' in s and '0' not in s:
		print('0')
	else:
		c = 0
		while s[0] == '1':
			s = s[1:]
		while s[-1] == '1':
			s = s[:-1]
		women = list(s.split('0'))
		for w in women:
			if len(w) == 1:
				c -= 1
			elif len(w) >= 2:
				c -= 2
		z = s.count('0') - 1
		c += 2 * z
		print(c)


def solve():
	n = int(input())
	a = input()
	ans = 0
	for x in range(n - 1):
		if a[x] == '0' and a[x + 1] == '0':
			ans += 2
		elif x + 2 < n and a[x] == '0' and (a[x + 1] == '1') and (a[x + 2] == '0'):
			ans += 1
	print(ans)
tst = int(input())
for i in range(tst):
	solve()


def main():
	n = int(input())
	line = input()
	res = 0
	for (i, c) in enumerate(line):
		if c == '1':
			continue
		if i + 1 < len(line) and line[i + 1] == '0':
			res += 2
		elif i + 2 < len(line) and line[i + 1:i + 3] == '10':
			res += 1
	return res
t = int(input())
print('\n'.join((str(main()) for _ in range(t))))


def solve(s):
	n0 = s.count('0')
	n1 = s.count('1')
	if n0 == 0:
		if n1 == 0:
			return 1
		else:
			return 0
	res = 0
	cnt = 2
	for i in range(len(s)):
		if s[i] == '0':
			if cnt < 2:
				res += 2 - cnt
			cnt = 0
		else:
			cnt += 1
	return res
t = int(input())
for _ in range(t):
	n = input()
	s = input()
	res = solve(s)
	print(res)


for i in range(int(input())):
	ab = int(input())
	abc = input()
	count = 0
	for j in range(ab):
		if abc[j] == '0':
			if j + 1 < ab and abc[j + 1] == '0':
				count += 2
			elif j + 2 < ab and abc[j + 2] == '0':
				count += 1
	print(count)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inp()
for i in range(n):
	k = inp()
	s = insr()
	count = 0
	if k == 1:
		print(0)
		continue
	if s[0] == s[1] and s[0] == '0':
		count += 2
	for j in range(1, k - 1):
		if s[j] == '0' and s[j + 1] == '0':
			count += 2
		if s[j] == '1' and s[j - 1] == '0' and (s[j + 1] == '0'):
			count += 1
	print(count)


for _ in range(int(input())):
	a = int(input())
	s = input()
	(o, z, ans) = (0, 0, 0)
	for i in range(a):
		if s[i] == '1':
			continue
		if i < a - 1 and s[i + 1] == '0':
			ans += 2
		elif i < a - 2 and s[i + 1] == '1' and (s[i + 2] == '0'):
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	(a, b) = (0, 0)
	ans = 0
	i = 0
	while i < n and st[i] != '0':
		i += 1
	c = 2
	while i < n:
		if st[i] == '0':
			if c < 2:
				ans += 2 - c
			c = 0
		else:
			c += 1
		i += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	num_str = input()
	last_zero_idx = -100
	total = 0
	for j in range(n):
		if num_str[j] == '0':
			if j - last_zero_idx == 1:
				total += 2
			elif j - last_zero_idx == 2:
				total += 1
			last_zero_idx = j
	print(total)


def cosplay(s):
	res = 0
	ct = 0
	seen = False
	for i in range(len(s)):
		if s[i] == '0':
			if not seen:
				seen = True
			else:
				if ct >= 2:
					pass
				else:
					res += 2 - ct
				ct = 0
		elif seen:
			ct += 1
	return res
t = int(input())
for x in range(t):
	n = int(input())
	s = input()
	ans = cosplay(s)
	print(ans)


import math, os, io, heapq
from functools import reduce
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product
import bisect

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	(n, s) = (getInt(), input())
	(ans, lst) = (0, -1)
	for i in range(n):
		if s[i] == '0':
			ones = i - lst - 1
			if lst >= 0 and ones < 2:
				ans += 2 - ones
			lst = i
	print(ans)
for _ in range(getInt()):
	solve()


t = int(input())
for i in range(t):
	input()
	line = input()
	count = 0
	for i in range(len(line) - 1):
		if line[i] == '0':
			if line[i + 1] == '0':
				count += 2
			elif i + 2 < len(line) and line[i + 2] == '0':
				count += 1
	print(count)


def beautiful(line: str):
	if len(line) < 3:
		if line == '00':
			return 2
		return 0
	db = {'000': (4, '10'), '001': (2, '01'), '010': (1, '10'), '011': (0, '11'), '100': (2, '10'), '101': (0, '01'), '110': (0, '10'), '111': (0, '11')}
	ans = 0
	last = line[0:2]
	for num in range(2, len(line)):
		(amt, last) = db[last + line[num]]
		ans += amt
	return ans
out_file = ''
num_test = int(input())
for i in range(num_test):
	length = input()
	string = input()
	out_file += f'{beautiful(string)}\n'
print(out_file)


for _ in range(int(input(''))):
	input()
	s = input()
	ans = 0
	cnt = 2
	for c in s:
		if c == '1':
			cnt += 1
		else:
			ans += max(2 - cnt, 0)
			cnt = 0
	print(ans)


n = int(input())
for i in range(n):
	x = input()
	s = input()
	total = 0
	while '00' in s or '010' in s:
		if '00' in s:
			y = s.count('00')
			s = s.replace('00', '0110')
			total += y * 2
		elif '010' in s:
			y = s.count('010')
			s = s.replace('010', '0110')
			total += y
	print(total)


for t in range(int(input())):
	n = int(input())
	a = input()
	x = -1
	sum = 0
	for i in range(n):
		if a[i] == '0':
			if x != -1:
				s = i - x
				if s == 1:
					sum += 2
				elif s == 2:
					sum += 1
			x = i
	print(sum)


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = input()
	x = 0
	count = 2
	for i in a:
		if i == '1':
			count += 1
		else:
			if 2 - count >= 0:
				x += 2 - count
			count = 0
	print(x)


num = int(input())
for i in range(num):
	n = int(input())
	str = input()
	l1 = len(str)
	while str.count('00') != 0 or str.count('010') != 0:
		str = str.replace('00', '0110')
		str = str.replace('010', '0110')
	l2 = len(str)
	print(l2 - l1)


def main():
	for t in range(int(input())):
		n = int(input())
		s = input()
		print(solver(s, n))

def solver(s, n):
	answ = 0
	i = 0
	s += '111111'
	while i < n:
		if s[i] == '0':
			if s[i + 1] == '0' and s[i + 2] == '0':
				answ += 4
				i += 2
				continue
			elif s[i + 1] == '0' and s[i + 2] == '1' and (s[i + 3] == '0'):
				answ += 3
				i += 2
				continue
			elif s[i + 1] == '0' and s[i + 2] == '1' and (s[i + 3] == '1'):
				answ += 2
				i += 2
				continue
			elif s[i + 1] == '1' and s[i + 2] == '0':
				answ += 1
				i += 2
				continue
			elif s[i + 1] == '1' and s[i + 2] == '1':
				answ += 0
				i += 2
				continue
		i += 1
	return answ
main()


for i in range(int(input())):
	l = int(input())
	x = input()
	a = 0
	for j in range(1, l):
		if x[j - 1] == '0' and x[j] == '0':
			a += 2
		elif j + 1 < l:
			if x[j - 1] == '0' and x[j] == '1' and (x[j + 1] == '0'):
				a += 1
	print(a)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = len(s)
	s = s.replace('010', '0110')
	s = s.replace('00', '0110')
	s = s.replace('010', '0110')
	s = s.replace('00', '0110')
	cc = len(s)
	print(cc - c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(prev_ind, ans) = (-3, 0)
	for i in range(n):
		if s[i] == '0':
			if prev_ind == i - 1:
				ans += 2
			elif prev_ind == i - 2:
				ans += 1
			prev_ind = i
	print(ans)


tc = int(input())
for _ in range(tc):
	n = input()
	x = input()
	op = 0
	cnt = 2
	for i in x:
		if i == '1':
			cnt += 1
		else:
			op += max(2 - cnt, 0)
			cnt = 0
	print(op)


from collections import Counter

def read_single_num():
	return int(input())

def read_nums():
	return [int(x) for x in input().split()]
t = read_single_num()
for i in range(t):
	n = read_single_num()
	s = input()
	(m, f) = (0, 2)
	ans = 0
	for ch in s:
		if ch == '0':
			if f < 2:
				ans += 2 - f
			f = 0
		else:
			f += 1
	print(ans)


T = int(input())
for _ in range(T):
	n = int(input())
	s = list(input())
	i = 0
	count = 0
	while i < n:
		if s[i] == '1':
			i += 1
			continue
		elif i + 1 < n:
			if s[i + 1] == '0':
				count += 2
				i += 1
				continue
			elif i + 2 < n:
				if s[i + 2] == '1':
					i += 3
					continue
				else:
					count += 1
					i += 1
			else:
				break
		else:
			break
	print(count)


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


def main():
	input()
	s = input()
	ans = 0
	prev = 2
	prev2 = 2
	for (i, symb) in enumerate(map(int, s)):
		if symb == prev == 0:
			ans += 2
			(prev2, prev) = (1, symb)
		elif symb == 0 and prev == 1 and (prev2 == 0):
			ans += 1
			(prev2, prev) = (1, symb)
		else:
			(prev2, prev) = (prev, symb)
	print(ans)
t = int(input())
for _ in range(t):
	main()


def Solve():
	n = int(input())
	s = input()
	d = []
	for i in range(len(s)):
		if s[i] == '0':
			d.append(i)
	c = 0
	for i in range(1, len(d)):
		if d[i] - d[i - 1] < 3:
			c = c + 3 - (d[i] - d[i - 1])
	print(c)
q = int(input())
while q > 0:
	Solve()
	q = q - 1


def solver():
	n = int(input())
	for _ in range(n):
		l = int(input())
		f = input()
		len_fin = 0
		for i in range(l):
			if f[i] != '1':
				if i < l - 1:
					if f[i + 1] == '0':
						len_fin += 2
					elif i < l - 2 and f[i + 2] == '0':
						len_fin += 1
		print(len_fin)
solver()


for _ in ' ' * int(input()):
	n = int(input())
	s = list(input())
	c = 0
	for i in range(1, n):
		if s[i] == '0':
			if s[i - 1] == '0':
				c += 2
			elif i > 1:
				if s[i - 2] == '0':
					c += 1
	print(c)


def main():
	n = int(input())
	s = input()
	ans = 0
	flag = 0
	cur = 0
	for i in range(n):
		if s[i] == '0':
			if flag == 0:
				flag = 1
				cur = 0
			else:
				ans += max(0, 2 - cur)
				cur = 0
		else:
			cur += 1
	print(ans)
t = int(input())
while t > 0:
	main()
	t -= 1


def solve():
	ans1 = 0
	for i in range(n - 1):
		if x[i] == '0' and x[i + 1] == '0':
			ans1 += 1
	ans2 = 0
	for i in range(n - 2):
		if x[i] == '0' and x[i + 1] == '1' and (x[i + 2] == '0'):
			ans2 += 1
	return ans1 * 2 + ans2
from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	x = input().strip()
	print(solve())


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	ans = 0
	for i in range(n - 2):
		if s[i] == '0':
			if s[i + 1] == '0':
				ans += 2
			elif s[i + 2] == '0':
				ans += 1
	if n >= 2:
		if s[-2:] == '00':
			ans += 2
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	Cos = input()
	Cos = Cos + ' '
	zeros = 0
	count = 0
	for q in range(len(Cos) - 1):
		if Cos[q] == '0' and Cos[q + 1] == '0':
			count += 2
		elif Cos[q] == '0' and Cos[q + 1] == '1' and (Cos[q + 2] == '0'):
			count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	count = 0
	prev_prev = ''
	prev = ''
	for c in s:
		if c == '0' and c == prev:
			count += 2
		elif c == '0' and prev == '1' and (prev_prev == '0'):
			count += 1
		prev_prev = prev
		prev = c
	print(count)


def make_great(ryad):
	n = 0
	for i in range(1, len(ryad)):
		if ryad[i - 1] == '0' and ryad[i] == '0':
			n += 2
		elif ryad[i - 1] == '0' and ryad[i] == '1':
			if i < len(ryad) - 1:
				if ryad[i + 1] == '0':
					n += 1
				else:
					pass
	return n
ms = []
a = int(input())
for i in range(a):
	b = int(input())
	s = input()
	ms.append(make_great(s))
for i in ms:
	print(i)


a = int(input())
for b in range(a):
	n = int(input())
	s = input()
	c = 0
	for i in range(n - 2):
		if s[i] == '0':
			if s[i + 1] == '0':
				c += 2
			elif s[i + 1] == '1':
				if s[i + 2] == '0':
					c += 1
	if s[-2:] == '00':
		c += 2
	print(c)


def function(n, s):
	count = 0
	i = 0
	prev = -3
	while i < n:
		if s[i] == '0':
			if i - prev == 1:
				count += 2
			elif i - prev == 2:
				count += 1
			prev = i
		i += 1
	return count

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		print(function(n, s))
main()


t = int(input())
for ele in range(t):
	n = int(input())
	s = input()
	cnt = 0
	for i in range(len(s) - 1):
		if s[i] == '0' and s[i + 1] == '0':
			cnt += 2
		elif s[i] == '0' and s[i + 1] == '1' and (i + 1 != len(s) - 1) and (s[i + 2] == '0'):
			cnt += 1
	print(cnt)


for j in range(int(input())):
	n = int(input())
	s = input()
	k = 0
	k1 = -1
	for i in range(n):
		if s[i] == '0':
			if -1 < k1 < 2:
				k = k + 2 - k1
			k1 = 0
		elif s[i] == '1' and k1 != -1:
			k1 += 1
	print(k)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(n - 1):
		if i == n - 2:
			if s[i] == '0' and s[i + 1] == '0':
				ans += 2
		elif s[i] == '0':
			if s[i + 1] == '1':
				if s[i + 2] == '1':
					continue
				else:
					ans += 1
			else:
				ans += 2
	print(ans)


rrr = int(input())
rr = []
lst1 = []
for j in range(rrr):
	n = int(input())
	lst = list(input())
	res = 0
	s = 0
	for i in range(len(lst) - 1):
		if lst[i] == '1' and lst[i - 1] == '0' and (lst[i + 1] == '0') and (i != 0):
			res += 1
		elif lst[i] == '0' and lst[i + 1] == '0':
			res += 2
	rr.append(str(res))
print('\n'.join(rr))


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


t = int(input())
for r in range(t):
	n = int(input())
	s = input()
	c = 0
	for i in range(len(s) - 1):
		if s[i] == '0':
			if s[i + 1] == '0':
				c += 2
			elif i != len(s) - 2:
				if s[i + 2] == '0':
					c += 1
	print(c)


for _ in range(int(input())):
	a = int(input())
	b = input()
	c = 0
	for i in range(len(b) - 1):
		if b[i] == '0' and b[i + 1] == '0':
			c += 2
		elif i != len(b) - 2 and (b[i] == '0' and b[i + 1] == '1' and (b[i + 2] == '0')):
			c += 1
	print(c)


T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	f = 0
	ans = 0
	pos = s.find('0')
	for i in range(pos + 1, n):
		if s[i] == '0':
			if f < 2:
				ans += 2 - f
			f = 0
		else:
			f += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	ret = 0
	s.append('\n')
	for i in range(n - 1):
		if s[i] == '0' and s[i + 1] == '0':
			ret += 2
		elif s[i] == '0' and s[i + 1] == '1' and (s[i + 2] == '0'):
			ret += 1
	print(ret)


t = int(input())
for t1 in range(t):
	n = int(input())
	s = input()
	l = list(s)
	flag = -1
	count = 0
	indi = -1
	for (x, y) in zip(l, l[1:]):
		indi += 1
		if x == '0' and y == '0':
			count += 2
		elif x == '0' and y == '1' and (indi + 2 < len(s)):
			if l[indi + 2] == '0':
				count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	count = 0
	d = 0
	z = -1
	for i in range(n):
		if s[i] == '0':
			if z > -1:
				if d < 2:
					count += 2 - d
			z = i
			d = 0
		elif s[i] == '1':
			d += 1
	print(count)


import sys
import math
import itertools
mod = 10 ** 9 + 7

def ri():
	return int(input())

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

def rls():
	return list(map(str, input().split()))

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

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def nextPowerOf2(n):
	n -= 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n += 1
	return n

def highestPowerof2(x):
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	return x ^ x >> 1
for _ in range(ri()):
	n = ri()
	s = input().split('1')
	c = 0
	for i in range(len(s) - 1):
		if s[i] != '' and s[i + 1] != '':
			c += 1
		if s[i] != '':
			co = s[i].count('0')
			c += (co - 1) * 2
	if s[-1] != '':
		co = s[-1].count('0')
		c += (co - 1) * 2
	print(c)


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

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
tc = inp()
while tc:
	length = inp()
	cosPlayers = insr()
	firstZero = -1
	secondZero = -1
	ind = 0
	OnesFound = 0
	totalPlayersNeeded = 0
	while ind != length:
		if cosPlayers[ind] == '0':
			if firstZero == -1:
				firstZero = ind
				OnesFound = 0
			else:
				if OnesFound < 2:
					totalPlayersNeeded += 2 - OnesFound
				OnesFound = 0
				firstZero = ind
		else:
			OnesFound += 1
		ind += 1
	print(totalPlayersNeeded)
	tc -= 1


import sys
import math
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(input())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def main():
	for t in range(get_int()):
		n = int(input())
		s = input()
		ans = 0
		for i in range(0, n - 1):
			if s[i] == '0' and s[i + 1] == '0':
				ans += 2
			elif i + 2 < n:
				if s[i] == '0' and s[i + 1] == '1' and (s[i + 2] == '0'):
					ans += 1
		print(ans)
main()


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


def solve():
	ans = 0
	n = input()
	k = input()
	ze = []
	for i in range(len(k)):
		if k[i] == '0':
			ze.append(i)
	for i in range(1, len(ze)):
		diff = ze[i] - ze[i - 1]
		if diff <= 2:
			ans += 3 - diff
	print(ans)
t = int(input())
for i in range(1, t + 1):
	solve()


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = 0
	lst = [*s, 'a', 'a']
	for i in range(n):
		if lst[i] == '0' and lst[i + 1] == '1' and (lst[i + 2] == '0'):
			cnt += 1
		if lst[i] == '0' and lst[i + 1] == '0':
			cnt += 2
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input()))
	ans = 0
	if n == 1:
		print(0)
	else:
		for i in range(n - 2):
			if s[i] == 0:
				if s[i + 1] == 0:
					ans += 2
				elif s[i + 2] == 0:
					ans += 1
		if s[n - 2] + s[n - 1] == 0:
			ans += 2
		print(ans)


a = int(input())
for j in range(a):
	b = int(input())
	c = input()
	d = 0
	for i in range(b - 1):
		if c[i] == '0' and c[i + 1] == '0':
			d = d + 2
		elif c[i] == '0' and c[i + 1] == '1' and (i != b - 2):
			if c[i + 2] == '0':
				d = d + 1
			else:
				pass
		else:
			pass
	print(d)


n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	l = len(s)
	ans = 0
	for j in range(l - 1):
		if s[j] == '0':
			if s[j + 1] == '0':
				ans += 2
			elif not j + 3 > l:
				if s[j + 2] == '0':
					ans += 1
	print(ans)


for u in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(n):
		if s[i:i + 2] == '00':
			ans += 2
		elif s[i:i + 3] == '010':
			ans += 1
	print(ans)


for _ in [0] * int(input()):
	n = int(input())
	s = input()
	t = 0
	for i in range(n):
		if s[i] == '0':
			if i + 2 < n:
				if s[i + 1] == '0':
					t = t + 2
				elif s[i + 2] == '0':
					t = t + 1
			elif i + 1 < n:
				if s[i + 1] == '0':
					t = t + 2
	print(t)


def check(n, s):
	z = 0
	one = 0
	total = 0
	ind = 0
	for i in range(n):
		if s[i] == '0':
			ind = i
			break
	for i in range(ind + 1, n):
		if s[i] == '0':
			val = i - ind - 1
			if val < 2:
				total += 2 - val
			ind = i
	return total
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(check(n, s))


T = int(input())
for t in range(T):
	s = -1
	f = 0
	f1 = 0
	n = int(input())
	row = input()
	for i in range(len(row)):
		if row[i] == '0':
			if s != -1:
				if i - s == 1:
					f = f + 2
				if i - s == 2:
					f = f + 1
			s = i
	print(f)


n = int(input())
for i in range(n):
	k = int(input())
	s = input()
	c = 2
	ans = 0
	for i in range(len(s)):
		if s[i] == '1':
			c += 1
		else:
			if c < 2:
				ans += 2 - c
			c = 0
	print(ans)


import sys
import math
data = sys.stdin.readlines()
numCases = int(data[0])
cases = []
for each in range(1, numCases + 1):
	input_ = data[each * 2].replace('\n', '')
	cases.append(input_)
for line in cases:
	res = 0
	prev_0 = -1
	for ind in range(len(line)):
		if line[ind] == '0':
			if prev_0 != -1:
				if ind - prev_0 == 1:
					res += 2
				elif ind - prev_0 == 2:
					res += 1
			prev_0 = ind
	print(res)


t = int(input())
for x in range(t):
	n = int(input())
	s = input()
	ans = 0
	cnt = 2
	for c in s:
		if c == '1':
			cnt += 1
		else:
			ans += max(2 - cnt, 0)
			cnt = 0
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	p = -1
	result = 0
	for i in range(n):
		if s[i] == '0':
			if p != -1:
				if i - p == 1:
					result += 2
				elif i - p == 2:
					result += 1
			p = i
	if n == 0 and s[0] == '0':
		print(1)
	else:
		print(result)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().rstrip()
	ans = 0
	cnt = 2
	for c in s:
		if c == '1':
			cnt += 1
		else:
			ans += max(2 - cnt, 0)
			cnt = 0
	print(ans)


import re
for _ in range(int(input())):
	x = int(input())
	y = input()
	print(2 * len(re.findall('(?=00)', y)) + len(re.findall('(?=010)', y)))


for _ in range(int(input())):
	n = int(input())
	l = input().strip()
	ans = 0
	for i in range(n - 1):
		if l[i] == l[i + 1]:
			if l[i] == '0':
				ans += 2
		elif i < n - 2 and l[i] == '0' and (l[i + 2] == '0'):
			ans += 1
	print(ans)