Read problems statements [Mandarin] , [Bengali] , [Hindi] , [Russian] and [Vietnamese] as well.

There are $N$ watchtowers built in a row. Each watchtower can only accommodate one person. Some of them are already occupied by members of the Night's Watch. Since the members of the Night's Watch do not get along, no two consecutive towers can be occupied at any moment.

Arya heard that the wildlings are planning an attack. She is not satisfied by the current security, so she plans to place more members of the Night's Watch in the empty towers. What is the maximum number of people she can place in the towers such that no two consecutive towers are occupied afterwards? Note that Arya may not remove anyone from already occupied towers.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The next line contains a single string $S$ with length $N$. For each valid $i$, the $i$-th character of this string is '1' if the $i$-th watchtower is initially occupied or '0' if it is empty.

------  Output ------
For each test case, print a single line containing one integer — the maximum number of people Arya can place in the towers.

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 10^{6}$
$S$ contains only characters '0' and '1'
initially, no two consecutive towers are occupied
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (20 points): initially, all towers are empty

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
2

6

010001

11

00101010000
----- Sample Output 1 ------ 
1

3

Source: codechef | Difficulty: MEDIUM
Tags: Implementation


Solutions:
for _ in range(int(input())):
	n = int(input())
	s = list(input().strip())
	lw = -2
	if n == 1:
		if s[0] == '0':
			print(1)
			continue
		else:
			print(0)
			continue
	elif n == 2:
		if s[0] == s[1] == '0':
			print(1)
			continue
		else:
			print(0)
			continue
	count = 0
	for i in range(n - 1):
		if s[i] == s[i + 1] == '0' and i - lw > 1:
			lw = i
			count += 1
		elif s[i] == '1':
			lw = i
	if s[-2] == s[-1] == '0' and n - 1 - lw > 1:
		print(count + 1)
	else:
		print(count)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	s = input().replace('01', '11').replace('10', '11')
	s += '1'
	cur = 0
	ans = 0
	for i in s:
		if i == '1':
			ans += ceil(cur / 2)
			cur = 0
		else:
			cur += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	st1 = input()
	count1 = 0
	count2 = 0
	count = 0
	final = 0
	j = 0
	list1 = []
	while j < n:
		if st1[j] == '1':
			break
		if st1[j] == '0':
			count1 += 1
		j += 1
	final += count1 // 2
	start = j + 1
	j = n - 1
	while j >= 0:
		if st1[j] == '1':
			break
		if st1[j] == '0':
			count2 += 1
		j -= 1
	final += count2 // 2
	end = j
	z = start
	while z <= end:
		if st1[z] == '0':
			count += 1
		else:
			list1.append(count)
			count = 0
		z += 1
	for v in list1:
		final += (v - 1) // 2
	if st1 == '0':
		print(1)
	elif '1' not in st1:
		print((len(st1) + 1) // 2)
	else:
		print(final)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	c = 0
	i = 0
	while i < len(s) - 1:
		if s[i] == '0' and s[i + 1] == '0':
			s = s[:i] + '1' + s[i + 1:]
			i += 1
			c += 1
		elif s[i] == '1':
			i += 1
		i += 1
	if s[n - 2] == '0' and s[n - 1] == '0':
		c += 1
	print(c)
	t -= 1


for t in range(int(input())):
	n = int(input())
	s = list(map(str, input()))
	c = 0
	if len(s) == 1 and s[0] == '0':
		print(1)
	else:
		for i in range(len(s)):
			if i == 0:
				if s[i] == '0':
					if s[i + 1] == '0':
						c += 1
						s[i] = '1'
			elif i == len(s) - 1:
				if s[i] == '0':
					if s[i - 1] == '0':
						c += 1
						s[i] = '1'
			elif s[i] == '0':
				if s[i + 1] == '0' and s[i - 1] == '0':
					c += 1
					s[i] = '1'
		print(c)


t = input()
for c in range(0, int(t)):
	n = input()
	s = input()
	count = 0
	flip = 0
	for x in range(0, int(n)):
		if int(n) == 1:
			count = 1
		elif x == 0 and int(n) > 1:
			if s[x] == '0' and s[x + 1] == '0':
				count = count + 1
				flip = 1
		elif x == int(n) - 1 and int(n) > 1 and (flip == 0):
			if s[x - 1] == '0' and s[x] == '0':
				count = count + 1
		elif flip == 0 and s[x - 1] == '0' and (s[x] == '0') and (s[x + 1] == '0'):
			count = count + 1
			flip = 1
		else:
			flip = 0
	print(count)


import math
for _ in range(int(input())):
	n = int(input())
	string = input()
	st = list(string)
	c = 0
	if '1' not in st:
		c = math.ceil(n / 2)
	else:
		if st[0] == '0' and st[1] == '0':
			st[0] = '1'
			c += 1
		if st[n - 2] == '0' and st[n - 1] == '0':
			st[n - 1] = '1'
			c += 1
		for i in range(1, n - 1):
			if st[i - 1] == '0' and st[i] == '0' and (st[i + 1] == '0'):
				st[i] = '1'
				c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	tower = input()
	wer = [int(d) for d in tower]
	indices = []
	for i in range(n):
		if wer[i] == 1:
			indices.append(i)
	add = 0
	end = len(indices)
	if end == 0:
		add += (n + 1) // 2
	else:
		for j in range(end + 1):
			if j == 0:
				add += indices[j] // 2
			elif j == end:
				add += (n - 1 - indices[j - 1]) // 2
			else:
				add += (indices[j] - indices[j - 1] - 2) // 2
	print(add)


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


import math
for i in range(int(input())):
	n = int(input())
	s = list(input())
	count = 0
	if '1' not in s:
		count = math.ceil(n / 2)
	else:
		if s[0:2] == ['0', '0']:
			s[0] = '1'
			count += 1
		if s[-1:-3:-1] == ['0', '0']:
			s[-1] = '1'
			count += 1
		for i in range(2, n - 2):
			if s[i:i + 2] == ['0', '0']:
				if s[i + 2] == '1' and s[i - 1] == '0':
					s[i] = '1'
					count += 1
				elif s[i - 1] == '1' and s[i + 2] == '0':
					s[i + 1] = '1'
					count += 1
				elif s[i + 2] == '1' and s[i - 1] == '1':
					count += 0
				elif s[i + 2] == '0' and s[i - 1] == '0':
					count += 2
					s[i + 2] = '1'
					s[i] = '1'
	print(count)


for _ in range(int(input())):
	no = int(input())
	st = input()
	c = 1
	s = 0
	for t in st:
		if t == '0':
			c += 1
		else:
			if c % 2 == 0:
				c -= 1
			if c > 1:
				s += c // 2
			c = 0
	if c > 1:
		s += c // 2
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	a = list(a)
	a.insert(0, '0')
	a.insert(0, '1')
	a.append('0')
	a.append('1')
	x1 = 0
	x2 = 0
	num_of_men_added = 0
	for j in range(n + 4):
		if a[j] is '1':
			x2 = j
			if j is 0:
				continue
			else:
				increment = 0
				if (x2 - x1) % 2 is 0:
					increment = (x2 - x1 - 2) // 2
				else:
					increment = (x2 - x1 - 3) // 2
				num_of_men_added += increment
				x1 = x2
		else:
			continue
	print(num_of_men_added)


t = int(input())
for _ in range(t):
	n = int(input())
	counter = 0
	s = input()
	if n <= 2:
		for i in range(n):
			if s[i] == '1':
				counter = -1
		if counter == -1:
			print('0')
		else:
			print('1')
	else:
		for i in range(n):
			if i == 0:
				k = s[0] + s[1] + s[2]
				if k == '001' or k == '000':
					s = '1' + s[1:]
					counter = counter + 1
			elif i == n - 1:
				k = s[n - 3] + s[n - 2] + s[n - 1]
				if k == '100' or k == '000':
					counter = counter + 1
			elif s[i] != '1':
				if s[i - 1] == '0' and s[i + 1] == '0':
					s = s[:i] + '1' + s[i + 1:]
					counter = counter + 1
		print(counter)


testcases = int(input())
numberoftowers = []
occupationoftowers = []
for x in range(testcases):
	numberoftowers.append(int(input()))
	occupationoftowers.append(list(input()))
	occupationoftowers[x] = list(map(int, occupationoftowers[x]))
for x in range(testcases):
	runningtotal = 0
	if len(occupationoftowers[x]) == 1:
		if occupationoftowers[x][0] == 0:
			occupationoftowers[x][0] = 1
			runningtotal += 1
	if occupationoftowers[x][0] == 0 and occupationoftowers[x][1] == 0:
		occupationoftowers[x][0] = 1
		runningtotal += 1
	if occupationoftowers[x][-1] == 0 and occupationoftowers[x][-2] == 0:
		occupationoftowers[x][-1] = 1
		runningtotal += 1
	for y in range(len(occupationoftowers[x]) - 2):
		if occupationoftowers[x][y] == 0 and occupationoftowers[x][y + 1] == 0 and (occupationoftowers[x][y + 2] == 0):
			runningtotal += 1
			occupationoftowers[x][y + 1] = 1
	print(runningtotal)


import math
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	(cnt, ans) = (0, 0)
	se = set(s)
	if len(se) == 1:
		if s[0] == '0':
			print(math.ceil(n / 2))
		else:
			print(0)
	else:
		for i in range(n):
			if i == 0 and s[i] == '0':
				if s[i + 1] == '0':
					cnt = cnt + 1
					s[i] = '1'
			elif i == n - 1 and s[i] == '0':
				if s[i - 1] == '0':
					s[i] = '1'
					cnt = cnt + 1
			elif s[i] == '0':
				if s[i - 1] == '0' and s[i + 1] == '0':
					cnt = cnt + 1
					s[i] = '1'
		print(cnt)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(input())
	if '1' not in a:
		if n % 2 == 0:
			print(n // 2)
		else:
			print(n // 2 + 1)
	else:
		c = 0
		for j in range(n):
			if j == 0:
				if a[j] == '0' and a[j + 1] == '0':
					a[j] = '1'
					c += 1
			if j != 0 and j != n - 1:
				if a[j - 1] == '0' and a[j] == '0' and (a[j + 1] == '0'):
					a[j] = '1'
					c += 1
			if j == n - 1:
				if a[j] == '0' and a[j - 1] == '0':
					a[j] = '1'
					c += 1
		print(c)


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


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	string = input()
	ans = 0
	zero_count = 0
	for j in range(length):
		if string[j] == '0':
			zero_count += 1
		else:
			add = zero_count // 2
			if zero_count & 1:
				ans += add
			elif j - zero_count != 0:
				ans += add - 1
			else:
				ans += add
			zero_count = 0
	if zero_count == length:
		ans += math.ceil(zero_count / 2)
	else:
		ans += zero_count // 2
	print(ans)


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(input())
	ans = 0
	if length == 1 and arr[0] == '0':
		ans = 1
	if length > 1 and arr[0] == '0' and (arr[1] == '0'):
		arr[0] = '1'
		ans = 1
	for j in range(1, length - 1):
		if arr[j - 1] == '0' and arr[j] == '0' and (arr[j + 1] == '0'):
			arr[j] = '1'
			ans += 1
	if length > 1 and arr[-2] == '0' and (arr[-1] == '0'):
		arr[-1] = '1'
		ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	tower = str(input())
	(cnt, prev, last) = (0, tower[0], tower[-1])
	if n == 1:
		print(abs(int(tower[0]) - 1))
		continue
	if '1' not in tower:
		print(-(n // -2))
		continue
	if tower[0] == '0' and tower[1] == '0':
		prev = '1'
		cnt += 1
	if tower[-1] == '0' and tower[-2] == '0':
		last = '1'
		cnt += 1
	for i in range(1, n - 1):
		end = tower[i + 1]
		if i == n - 2:
			end = last
		if prev == '0' and tower[i] == '0' and (end == '0'):
			cnt += 1
			prev = '1'
		else:
			prev = tower[i]
	print(cnt)


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


for _ in range(int(input())):
	n = int(input())
	(t, c) = (input(), 0)
	if not '1' in t:
		if n % 2 == 0:
			print(n // 2)
		else:
			print(n // 2 + 1)
		continue
	t = list(t)
	if t[0] == '0' and t[1] == '0':
		c += 1
		t[0] = '1'
	if t[n - 1] == '0' and t[n - 2] == '0':
		c += 1
		t[n - 1] = '1'
	for i in range(1, n - 1):
		if t[i] == '0':
			if t[i + 1] == '0' and t[i - 1] == '0':
				t[i] = '1'
				c += 1
	print(c)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	l = [int(i) for i in s]
	out = 0
	if n == 1:
		if l[0] == 0:
			out += 1
	elif n == 2:
		if l[0] == 0 and l[1] == 0:
			out += 1
	elif n > 2:
		if l[0] == 0 and l[1] == 0:
			l[0] = 1
			out += 1
		for i in range(1, n - 1):
			if l[i - 1] == 0 and l[i + 1] == 0 and (l[i] == 0):
				l[i] = 1
				out += 1
		if l[n - 1] == 0 and l[n - 2] == 0:
			l[n - 1] = 1
			out += 1
	print(out)


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


for tc in range(int(input())):
	n = int(input())
	a = input()
	if a.count('1') == 0:
		print((n + 1) // 2)
	else:
		c = 0
		p = 0
		r = 0
		for i in range(n):
			if a[i] == '0':
				c += 1
			else:
				p += c // 2
				break
		for i in range(n - 1, -1, -1):
			if a[i] == '0':
				r += 1
			else:
				p += r // 2
				break
		z = 0
		for i in range(c, n - r):
			if a[i] == '0':
				z += 1
			else:
				if z >= 3:
					p += (z - 1) // 2
				z = 0
		print(p)


for _ in range(int(input())):
	input()
	S = input()
	k = 0
	total = 0
	starting = True
	for c in S:
		if c == '0':
			k += 1
		elif k:
			total += (k if starting else k - 1) // 2
			k = 0
			starting = False
	if k:
		total += (k + 1 if starting else k) // 2
	print(total)


t = int(input())
for i in range(t):
	n = int(input())
	a = str(input())
	c = 0
	m = 0
	if n == 1:
		if a == '0':
			print(1)
		else:
			print(0)
	elif n == 2:
		if a == '00':
			print(1)
		else:
			print(0)
	else:
		if a[0] == '0' and a[1] == '0':
			m += 1
		if a[n - 1] == '0' and a[n - 2] == '0':
			m += 1
		for j in range(1, n - 1):
			if a[j] == '0':
				c += 1
			if a[j] == '1':
				c = 0
			if c == 3:
				m += 1
				c = 1
		print(m)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l = list(s)
	ans = 0
	if '1' not in l:
		if n % 2 == 0:
			print(n // 2)
		else:
			print((n + 1) // 2)
		continue
	for j in range(n):
		if j == 0 and l[j] == '0' and (l[j + 1] == '0'):
			ans += 1
			l[0] = '1'
		if j == n - 1 and l[j] == '0' and (l[j - 1] == '0'):
			ans += 1
			l[j] = '1'
		if l[j] == '0' and l[j - 1] == '0' and (l[j + 1] == '0'):
			ans += 1
			l[j] = '1'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = input()
	a1 = list(a)
	c = 0
	if n == 1 and a1[0] == '0':
		c = 1
		print(c)
	else:
		for i in range(n):
			if i == 0:
				if a1[i] == '0':
					if a1[i + 1] == '0':
						c += 1
						a1[i] = 1
			elif i == n - 1:
				if a1[i] == '0':
					if a1[i - 1] == '0':
						c += 1
						a1[i] = 1
			elif a1[i] == '0':
				if a1[i - 1] == '0' and a1[i + 1] == '0':
					c += 1
					a1[i] = 1
		print(c)


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


t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	st = list(st)
	count = 0
	if len(st) == 1 and st[0] == '0':
		count = 1
		print(count)
	else:
		for i in range(len(st)):
			if i == 0:
				if st[i] == '0':
					if st[i + 1] == '0':
						count += 1
						st[i] = '1'
			elif i == len(st) - 1:
				if st[i] == '0':
					if st[i - 1] == '0':
						count += 1
						st[i] = '1'
			elif st[i] == '0':
				if st[i + 1] == '0' and st[i - 1] == '0':
					count += 1
					st[i] = '1'
		print(count)


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


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	word = input()
	total = 0
	for i in range(n):
		if word[i] == '0':
			prev = word[i - 1] == '0' if i != 0 else True
			next = word[i + 1] == '0' if i != n - 1 else True
			if prev and next:
				total += 1
				word = word[:i] + '1' + word[i + 1:]
	print(total)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	pat = list((i for i in s))
	if '1' in pat:
		count = 0
		for j in range(n):
			if j == 0 and int(pat[j]) == 0 and (int(pat[j + 1]) == 0):
				pat[j] = 1
				count += 1
			elif j == n - 1 and int(pat[j - 1]) == 0 and (int(pat[j]) == 0):
				pat[j] = 1
				count += 1
			elif int(pat[j]) == 0 and int(pat[j - 1]) == 0 and (int(pat[j + 1]) == 0):
				pat[j] = 1
				count += 1
		print(count)
	else:
		print(int(n / 2 if n % 2 == 0 else n / 2 + 1))


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


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(count, st, en) = (0, 1, n - 1)
	if s.count('1') == 0:
		print((n + 1) // 2)
	else:
		if s[0] == '0' and s[1] == '0':
			count += 1
			st += 1
		if s[n - 1] == '0' and s[n - 2] == '0':
			count += 1
			en -= 1
		while st < en:
			if s[st - 1] == '0' and s[st] == '0' and (s[st + 1] == '0'):
				count += 1
				st += 2
			else:
				st += 1
		print(count)


import re
pattern = '(0{3,})'
for _ in range(int(input())):
	n = int(input())
	s = input()
	extraMen = 0
	if n == 1 and s == '0':
		print(1)
		continue
	if s.startswith('00'):
		extraMen += 1
		s = '1' + s[1:]
	if s.endswith('00'):
		extraMen += 1
		s = s[:-1] + '1'
	for found in re.findall(pattern, s):
		extraMen += (len(found) - 1) // 2
	print(extraMen)


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	count = 0
	start = 0
	if '1' not in s:
		print(math.ceil(n / 2))
		continue
	for i in range(n):
		if s[i] == '0':
			count += 1
		else:
			if count % 2 != 0 or start == 0:
				ans += count // 2
			else:
				ans += max(count // 2 - 1, 0)
			count = 0
			start = 1
	print(ans + count // 2)


import sys
input = sys.stdin.readline

def rii():
	return range(int(input().strip()))

def ii():
	return int(input().strip())

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())
import re
regex = '(0{3,})'

def solve(*args):
	(n, s) = args
	added = 0
	if n == 1 and s == '0':
		return 1
	if s.startswith('00'):
		s = '1' + s[1:]
		added += 1
	if s.endswith('00'):
		s = s[:-1] + '1'
		added += 1
	for r in re.findall(regex, s):
		added += (len(r) - 1) // 2
	return added

def do_codechef():
	for t in rii():
		n = ii()
		s = si()
		print(solve(n, s))
do_codechef()
exit()


T = int(input())
for i in range(T):
	n = int(input())
	s = list(map(str, input()))
	flag = 0
	if n >= 3:
		if s[1] == '0' and s[0] == '0':
			flag += 1
			s[0] = '1'
		if s[n - 1] == '0' and s[n - 2] == '0':
			flag += 1
			s[n - 1] = '1'
		for j in range(1, n - 1):
			if s[j - 1] == '0' and s[j + 1] == '0' and (s[j] == '0'):
				flag += 1
				s[j] = '1'
	else:
		if n == 1:
			if s[0] == '0':
				flag += 1
		if n == 2:
			if s[0] == '0' and s[1] == '0':
				flag += 1
	print(flag)


t = int(input())
for _ in range(t):
	n = int(input())
	new = input()
	inp = []
	c = 0
	for i in new:
		inp.append(i)
	if n == 1:
		if inp[0] == '0':
			print('1')
		else:
			print('0')
	else:
		for i in range(n):
			if i == 0:
				if inp[i] == '0' and inp[i + 1] == '0':
					inp[i] = '1'
					c += 1
			elif i > 0 and i < n - 1:
				if inp[i - 1] == '0' and inp[i] == '0' and (inp[i + 1] == '0'):
					inp[i] = '1'
					c += 1
			elif i == n - 1:
				if inp[i - 1] == '0' and inp[i] == '0':
					inp[i] == '1'
					c += 1
		print(c)


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


for _ in range(int(input())):
	n = int(input())
	str = input()
	p = '0' + str + '0'
	s = list(p)
	count = 0
	cur = 1
	prev = cur - 1
	next = cur + 1
	while next < len(s):
		if s[cur] == '0' and s[prev] == '0' and (s[next] == '0'):
			count = count + 1
			s[cur] = '1'
			cur = cur + 1
			prev = cur - 1
			next = cur + 1
		else:
			cur = cur + 1
			prev = cur - 1
			next = cur + 1
	print(count)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	g = 0
	count = 0
	if s.count('1') == 0:
		print(math.ceil(n / 2))
		continue
	for i in range(len(s)):
		if i == 0:
			if s[i + 1] != '1' and s[i] == '0':
				s = '1' + s[i + 1:]
				count = count + 1
		elif i == n - 1:
			if s[i - 1] != '1' and s[i] == '0':
				s = s[0:i] + '1'
				count = count + 1
		elif s[i - 1] != '1' and s[i + 1] != '1' and (s[i] == '0'):
			s = s[:i] + '1' + s[i + 1:]
			count = count + 1
	print(count)


t = int(input())
for r in range(t):
	count = 0
	n = int(input())
	s = input()
	lst = [int(a) for a in s]
	l = len(lst)
	if 1 not in lst:
		if l % 2 == 0:
			print(int(l / 2))
		else:
			print(int(l / 2) + 1)
	else:
		for i in range(l):
			if i == 0:
				if lst[i] == 0 and lst[i + 1] == 0:
					lst[i] = 1
					count = count + 1
			elif i == l - 1:
				if lst[i] == 0 and lst[i - 1] == 0:
					lst[i] = 1
					count = count + 1
			elif i >= 1 and i < l - 1:
				if lst[i] == 0:
					if lst[i + 1] == 0 and lst[i - 1] == 0:
						lst[i] = 1
						count = count + 1
		print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input()))
	count = 0
	if sum(arr) == 0:
		if n % 2 == 0:
			print(n // 2)
		else:
			print(n // 2 + 1)
		continue
	for i in range(n - 1):
		if arr[i] == -1:
			continue
		if arr[i] == 0:
			if arr[i + 1] == 0:
				arr[i] = 1
				arr[i + 1] = -1
				count += 1
		else:
			arr[i + 1] = -1
			continue
	if arr[n - 1] == 0 and arr[n - 2] == -1:
		count += 1
	print(count)


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


t = int(input())
for _ in range(t):
	N = int(input())
	S = input()
	L = list(S)
	c = 0
	flag = 0
	if '1' not in L:
		flag = 1
	if flag == 0:
		for i in range(len(S)):
			if i == 0:
				if L[i] != '1' and L[i + 1] != '1':
					L[i] = '1'
					c += 1
			elif i == len(S) - 1:
				if L[i] != '1' and L[i - 1] != '1':
					L[i] = '1'
					c += 1
					break
			elif L[i] != '1' and L[i + 1] != '1' and (L[i - 1] != '1'):
				L[i] = '1'
				c += 1
		print(c)
	if flag == 1:
		if N % 2 != 0:
			print(N // 2 + 1)
		else:
			print(N // 2)


try:
	for _ in range(int(input())):
		n = int(input())
		s = input()
		s = list(s)
		cnt = 0
		if '1' in s:
			ind = s.index('1')
			if ind != 0:
				cnt += ind // 2
			for i in range(ind + 1, n, 1):
				if s[i] == '1':
					diff = i - ind - 1
					if diff % 2 != 0:
						cnt += diff // 2
					else:
						cnt += diff // 2 - 1
					ind = i
			if ind != n - 1:
				diff = n - 1 - ind
				cnt += diff // 2
			print(cnt)
		elif n % 2 != 0:
			print(n // 2 + 1)
		else:
			print(n // 2)
except EOFError:
	pass


for _ in range(int(input())):
	N = int(input())
	S = input()
	if N == 1:
		if S == '0':
			print(1)
		else:
			print('0')
		continue
	if N == 2:
		if S == '00':
			print('1')
		else:
			print('0')
		continue
	S = list(S)
	ans = 0
	if S[0] == '0' and S[1] == '0':
		S[0] = '1'
		ans += 1
	for i in range(2, N - 1):
		if S[i] != '1' and S[i - 1] != '1' and (S[i + 1] != '1'):
			S[i] = '1'
			ans += 1
	if S[N - 1] == '0' and S[N - 2] == '0':
		ans += 1
	print(ans)


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


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	c = 0
	if '1' not in s:
		if n % 2 == 0:
			print(n // 2)
		else:
			print(n // 2 + 1)
	else:
		s = list(s)
		for i in range(1, n - 1):
			if s[0] == '0' and s[1] != '1':
				c += 1
				s[0] = '1'
			if s[i] == '0' and s[i + 1] != '1' and (s[i - 1] != '1'):
				s[i] = '1'
				c += 1
			elif s[-1] == '0' and s[-2] != '1':
				s[-1] = '1'
				c += 1
		print(c)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	status = list(input())
	ans = 0
	if status == ['0']:
		print(1)
		continue
	for i in range(n):
		if status[i] == '0':
			if i == 0:
				if status[i + 1] != '1':
					status[i] = '1'
					ans += 1
			elif i == n - 1:
				if status[i - 1] != '1':
					status[i] = '1'
					ans += 1
			elif status[i - 1] == status[i + 1] == '0':
				status[i] = '1'
				ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	z = 0
	if '1' not in s:
		if n % 2 != 0:
			print(int(n / 2) + 1)
		else:
			print(int(n / 2))
	else:
		s = list(s)
		for i in range(1, n - 1):
			if s[0] == '0' and s[1] != '1':
				c += 1
				s[0] = '1'
			if s[i] == '0' and s[i + 1] != '1' and (s[i - 1] != '1'):
				s[i] = '1'
				c += 1
			elif s[-1] == '0' and s[-2] != '1':
				s[-1] = '1'
				c += 1
		print(c)


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


for _ in range(int(input())):
	v = int(input())
	n = [i for i in str(input())]
	ans = 0
	if len(n) == 1:
		if n[0] == '1':
			print(0)
		else:
			print(1)
	else:
		for i in range(len(n)):
			if n[i] == '1':
				continue
			if i == 0:
				if n[1] == '0':
					n[0] = '1'
					ans += 1
			elif i == len(n) - 1:
				if n[i - 1] == '0':
					ans += 1
					break
			elif n[i - 1] == n[i + 1] == '0':
				ans += 1
				n[i] = '1'
		print(ans)


for _ in range(int(input())):
	n = int(input())
	if n == 0:
		print(0)
	else:
		lst = input()
		z = '0'
		v = '1'
		ans = 0
		ones = 0
		zeros = 0
		for i in lst:
			if i == '0':
				zeros += 1
			else:
				ones += 1
		if n == 1:
			if lst[0] == v:
				print(0)
			else:
				print(1)
		elif n == 2:
			if lst[0] == z and lst[1] == z:
				print(1)
			else:
				print(0)
		elif n >= 3:
			cc = 0
			if lst[0] == z and lst[1] == z:
				cc += 1
			if lst[n - 1] == z and lst[n - 2] == z:
				cc += 1
			i = 2
			while i < n - 2:
				if lst[i] == z:
					if lst[i - 1] == z and lst[i + 1] == z:
						cc += 1
						i += 2
					elif lst[i - 1] == '1':
						i += 1
					else:
						i += 3
				else:
					i += 1
			print(cc)


try:
	t = int(input())
	while t:
		flag = 0
		count = 0
		n = int(input())
		s = input()
		l = list(map(int, s))
		m = [-1]
		for i in range(0, n):
			if l[i] == 1:
				m.append(i + 1)
		m.append(n + 2)
		for i in range(0, len(m) - 1):
			diff = m[i + 1] - m[i] - 1
			if diff - 2 < 0:
				continue
			elif (diff - 2) % 2 == 0:
				count += (diff - 2) // 2
			else:
				count += 1 + (diff - 2) // 2
		print(count)
		t -= 1
except:
	pass


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


t = int(input())
for you in range(t):
	n = int(input())
	li = input()
	l = [int(i) for i in li]
	i = 0
	count = 0
	if n > 1:
		if l[0] == 0 and l[1] == 0:
			count += 1
			i += 1
		if l[n - 1] == 0 and l[n - 2] == 0:
			count += 1
			l[n - 1] = 1
		while i < n - 2:
			if l[i + 1] == 0 and l[i + 2] == 0 and (l[i] == 0):
				count += 1
				i += 2
			else:
				i += 1
		print(count)
	elif l[0] == 0:
		print(1)
	else:
		print(0)