The Little Elephant from the Zoo of Lviv currently is on the military mission. There are N enemy buildings placed in a row and numbered from left to right strating from 0. Each building i (except the first and the last) has exactly two adjacent buildings with indices i-1 and i+1. The first and the last buildings have just a single adjacent building.

Some of the buildings contain bombs. When bomb explodes in some building it destroys it and all adjacent to it buildings.

You are given the string S of length N, where S_{i} is 1 if the i-th building contains bomb, 0 otherwise. Find for the Little Elephant the number of buildings that will not be destroyed after all bombs explode. Please note that all bombs explode simultaneously.

------ Input ------ 

The first line contains single integer T - the number of test cases. T test cases follow. The first line of each test case contains the single integer N - the number of buildings. The next line contains the string S of length N consisted only of digits 0 and 1.

------ Output ------ 

In T lines print T inetgers - the answers for the corresponding test cases.

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

1 ≤ T ≤ 100

1 ≤ N ≤ 1000

----- Sample Input 1 ------ 
3
3
010
5
10001
7
0000000
----- Sample Output 1 ------ 
0
1
7

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures

Implementation


Solutions:
results = []
for _ in range(int(input())):
	(N, s) = (int(input()), input())
	l = list(s)
	for i in range(N):
		if s[i] == '1':
			l[i] = 'd'
			if i > 0:
				l[i - 1] = 'd'
			if i < N - 1:
				l[i + 1] = 'd'
	destroyed = 0
	for ele in l:
		if ele == 'd':
			destroyed += 1
	results.append(N - destroyed)
for ele in results:
	print(ele)


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


for item in range(int(input())):
	kp = int(input())
	pen = input()
	yan = [1] * kp
	for l in range(kp):
		if pen[l] == '1':
			yan[l] = 0
			if l != 0:
				yan[l - 1] = 0
			if l != kp - 1:
				yan[l + 1] = 0
	print(yan.count(1))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s = s.replace('010', 'aaa')
	s = s.replace('01', 'aa')
	s = s.replace('10', 'aa')
	c = s.count('0')
	print(c)


for _ in range(int(input())):
	N = int(input())
	S = input()
	S = S.replace('010', 'x')
	S = S.replace('10', 'x')
	S = S.replace('01', 'x')
	print(S.count('0'))


for i in range(int(input())):
	n = int(input())
	s = input()
	s = s.replace('010', 'xxx')
	s = s.replace('101', 'xxx')
	s = s.replace('10', 'xx')
	s = s.replace('01', 'xx')
	print(s.count('0'))


t = int(input())
for i in range(0, t):
	n = int(input())
	x = input()
	x = x.replace('010', 'xxx').replace('10', 'xx').replace('01', 'xx')
	print(x.count('0'))


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	s = stdin.readline().strip()
	x = s
	if n == 1:
		print(1 if s == '0' else 0)
		continue
	if n == 2:
		print(2 if s == '00' else 0)
		continue
	if s.count('1') >= n - 1:
		print(0)
		continue
	a = s.count('010') * 3
	s = s.replace('010', 'xxx')
	b = s.count('10') * 2
	s = s.replace('10', 'xx')
	c = s.count('01') * 2
	s = s.replace('01', 'xx')
	q = s.count('1')
	print(n - a - b - c - q)


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


for _ in range(int(input())):
	N = int(input())
	S = input()
	count = 0
	for (i, v) in enumerate(S):
		if v == '0':
			if not (i > 0 and S[i - 1] == '1' or (i < len(S) - 1 and S[i + 1] == '1')):
				count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	k = [0] * n
	for i in range(n):
		if s[i] == '1':
			k[i] = 1
			if i != 0:
				k[i - 1] = 1
			if i != n - 1:
				k[i + 1] = 1
	print(k.count(0))


for _ in range(int(input())):
	N = int(input())
	S = input().strip()
	left = N - S.count('1') - (S[:2] == '01') - S.count('10') - S.count('001')
	print(left)


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


tests = int(input())
for i in range(tests):
	length = int(input())
	string = input()
	if length == 1:
		if string[0] == '1':
			print(0)
		else:
			print(1)
	else:
		ans = 0
		for j in range(length):
			if string[j] == '0':
				if j == 0:
					if string[j + 1] == '0':
						ans += 1
				elif j == length - 1:
					if string[j - 1] == '0':
						ans += 1
				elif string[j - 1] == '0' and string[j + 1] == '0':
					ans += 1
		print(ans)


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


for _ in range(int(input())):
	n = int(input())
	s = input()
	new = s.replace('01', 'x1').replace('10', '1x')
	print(new.count('0'))


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	ind = set()
	while i < n:
		if s[i] == '1':
			ind.add(i)
			j = i + 1
			if i - 1 >= 0 and s[i - 1] == '0':
				ind.add(i - 1)
			while j < n and s[j] == '1':
				ind.add(j)
				j += 1
			if j < n and s[j] == '0':
				ind.add(j)
			i = j
		i += 1
	print(n - len(ind))


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = [0] * n
	c = 0
	for i in range(len(s)):
		if s[i] == '1':
			l[i] = True
			if i != 0:
				l[i - 1] = True
			if i != n - 1:
				l[i + 1] = True
	for i in l:
		if i == 0:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = input()
	a = a.replace('010', 'xxx')
	a = a.replace('10', 'xx')
	a = a.replace('01', 'xx')
	print(a.count('0'))


t = int(input())
while t:
	n = int(input())
	s = list(input())
	lis = [0] * n
	for i in range(n):
		if s[i] == '1':
			lis[i] = 1
			if i != n - 1:
				lis[i + 1] = 1
			if i != 0:
				lis[i - 1] = 1
	print(lis.count(0))
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	s = s.replace('010', 'aaa')
	s = s.replace('10', 'bb')
	s = s.replace('01', 'cc')
	print(s.count('0'))
	t = t - 1


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	s = stdin.readline().strip()
	a = s.count('010') * 3
	s = s.replace('010', 'xxx')
	b = s.count('10') * 2
	s = s.replace('10', 'xx')
	c = s.count('01') * 2
	s = s.replace('01', 'xx')
	q = s.count('1')
	print(n - a - b - c - q)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	visited = [False for _ in range(n)]
	for i in range(n):
		if s[i] == '1':
			visited[i] = True
			if i != n - 1:
				visited[i + 1] = True
			if i > 0:
				visited[i - 1] = True
	print(visited.count(False))


t = int(input())
for i in range(t):
	a = int(input())
	b = input()
	if a >= 3:
		x = 1
		list1 = []
		list1.append(int(b[0]) + int(b[1]))
		while x < a - 1:
			list1.append(int(b[x - 1]) + int(b[x]) + int(b[x + 1]))
			x += 1
		list1.append(int(b[a - 2]) + int(b[a - 1]))
		count = 0
		for k in list1:
			if k == 0:
				count += 1
		print(count)
	elif '1' in b:
		print(0)
	else:
		print(a)


for t in range(int(input())):
	n = int(input())
	s = input()
	k = []
	p = 0
	for i in s:
		if i == '1':
			k.append(p)
			p += 1
		else:
			p += 1
	l = k.copy()
	for i in k:
		l.append(i - 1)
		l.append(i + 1)
	s = list(s)
	for i in l:
		if i >= 0 and i < len(s):
			s[i] = -1
	print(s.count('0'))


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = n
	s = s.replace('010', 'xxx').replace('10', 'xx').replace('01', 'xx')
	print(s.count('0'))


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	s = stdin.readline().strip()
	s = s.replace('010', 'xxx').replace('10', 'xx').replace('01', 'xx')
	print(s.count('0'))


try:
	for _ in range(int(input())):
		n = int(input())
		a = list(input())
		l = ['0'] * n
		for i in range(n):
			if a[i] == '1':
				l[i] = '1'
				if i != 0:
					l[i - 1] = '1'
				if i != n - 1:
					l[i + 1] = '1'
		print(l.count('0'))
except:
	pass


for _ in range(int(input())):
	n = int(input())
	s = input()
	s = s.replace('10', '11')
	s = s.replace('01', '11')
	print(s.count('0'))


for tc in range(int(input())):
	n = int(input())
	buildings = input()
	count = 0
	if n == 1:
		if buildings[0] == '1':
			print(0)
		else:
			print(1)
	else:
		for i in range(n):
			if i == 0:
				if buildings[i] == '1' or buildings[i + 1] == '1':
					count += 1
			elif i == n - 1:
				if buildings[i] == '1' or buildings[i - 1] == '1':
					count += 1
			elif buildings[i] == '1' or buildings[i - 1] == '1' or buildings[i + 1] == '1':
				count += 1
		print(n - count)


for t in range(int(input())):
	n = int(input())
	s = input()
	s = s.replace('010', 'xxx').replace('10', 'xx').replace('01', 'xx')
	print(s.count('0'))


testcases = int(input())
for i in range(testcases):
	n = int(input())
	data = str(input())
	data = data.replace('010', 'xxx')
	data = data.replace('10', 'xx')
	data = data.replace('01', 'xx')
	print(data.count('0'))


for _ in range(int(input())):
	n = int(input())
	l = list(input())
	visit = [False] * n
	for i in range(n):
		if l[i] == '1':
			visit[i] = True
			if i != n - 1:
				visit[i + 1] = True
			if i != 0:
				visit[i - 1] = True
	print(visit.count(False))


for _ in range(int(input())):
	N = int(input())
	s = input()
	s = s.replace('010', '!!!')
	s = s.replace('10', 'xx')
	s = s.replace('01', 'yy')
	print(s.count('0'))


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


for i in range(int(input())):
	n = int(input())
	s = input()
	s = s.replace('010', ' ')
	s = s.replace('10', ' ')
	s = s.replace('01', ' ')
	print(s.count('0'))


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


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	new = s.replace('01', 'x1').replace('10', '1x')
	print(new.count('0'))


T = int(input())
for i in range(T):
	N = int(input())
	s = input()
	s = s.replace('010', 'XXX')
	s = s.replace('01', 'XX')
	s = s.replace('10', 'XX')
	print(s.count('0'))


for i in range(int(input())):
	t = int(input())
	a = input()
	a = a.replace('10', '11')
	a = a.replace('01', '11')
	print(a.count('0'))


import sys, math
I = sys.stdin.readline
O = sys.stdout.write

def solve(s, n):
	if n == 1:
		if s[0] == '1':
			return 0
		return 1
	res = 0
	arr = [1 for _ in range(n)]
	for (i, x) in enumerate(s):
		if i == 0:
			if x == '1':
				(arr[i], arr[i + 1]) = (0, 0)
		elif i == n - 1:
			if x == '1':
				(arr[i - 1], arr[i]) = (0, 0)
		elif x == '1':
			(arr[i], arr[i - 1], arr[i + 1]) = (0, 0, 0)
	return sum(arr)
t = int(I())
for _ in range(t):
	n = int(I())
	s = I()
	O(str(solve(s, n)) + '\n')


numInp = lambda : int(input())
lstImp = lambda : list(map(int, input().split()))
strImp = lambda : input()
spacedStrImp = lambda : list(input())
seperateImp = lambda : map(int, input().split())
for i in range(int(input())):
	numOfBuildings = numInp()
	buildings = strImp()
	detonations = list(buildings)
	for i in range(numOfBuildings):
		if int(buildings[i]):
			detonations[i] = True
			if i:
				detonations[i - 1] = True
			if i < numOfBuildings - 1:
				detonations[i + 1] = True
	safe = numOfBuildings - detonations.count(True)
	print(safe)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	l = ['0'] * n
	for i in range(n):
		if s[i] == '1':
			l[i] = '1'
			if i != 0:
				l[i - 1] = '1'
			if i != n - 1:
				l[i + 1] = '1'
	c = l.count('0')
	print(c)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s = s.replace('010', 'xxx')
	s = s.replace('01', 'xx')
	s = s.replace('10', 'xx')
	print(s.count('0'))


for i in range(int(input())):
	length = int(input())
	string = input()
	total = 0
	for i in range(length):
		if string[i] == '1':
			pass
		elif i > 0 and string[i - 1] == '1':
			pass
		elif i < length - 1 and string[i + 1] == '1':
			pass
		else:
			total += 1
	print(total)


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


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	s = stdin.readline().strip()
	x = s
	if n == 1:
		print(1 if s == '0' else 0)
		continue
	if n == 2:
		print(2 if s == '00' else 0)
		continue
	if n == 3:
		print(3 if s == '000' else 1 if s == '001' or s == '100' else 0)
		continue
	if n == 4:
		print(4 if s == '0000' else 2 if s == '0001' or s == '1000' else 1 if s == '0100' or s == '0010' or s == '0011' or (s == '1100') else 0)
		continue
	if s.count('0') == n:
		print(n)
		continue
	if s.count('1') >= n - 1:
		print(0)
		continue
	a = s.count('010') * 3
	s = s.replace('010', 'xxx')
	b = s.count('10') * 2
	s = s.replace('10', 'xx')
	c = s.count('01') * 2
	s = s.replace('01', 'xx')
	q = s.count('1')
	print(n - a - b - c - q)