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 Si 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

-----Example-----
Input:
3
3
010
5
10001
7
0000000

Output:
0
1
7

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
T = int(sys.stdin.readline().strip())
for t in range(T):
	sys.stdin.readline().strip()
	st = '0' + sys.stdin.readline().strip() + '0'
	res = 0
	for i in range(1, len(st) - 1):
		if st[i] == st[i - 1] == st[i + 1] == '0':
			res += 1
	print(res)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	c = 0
	z = 1
	for i in range(n):
		if s[i] == '0':
			z += 1
			continue
		if z > 2:
			c += z - 2
		z = 0
	if z > 1:
		c += z - 1
	t -= 1
	print(c)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = input()
	b = [1] * n
	for i in range(0, n):
		if a[i] == '1':
			b[i] = 0
			if i > 0:
				b[i - 1] = 0
			if i < n - 1:
				b[i + 1] = 0
	ans = 0
	for i in range(0, n):
		if b[i] == 1:
			ans += 1
	print(ans)


inputs = int(input())
while inputs > 0:
	length = int(input())
	building = input()
	buildings = []
	if length != 0:
		for i in range(0, length):
			buildings.append(int(building[i]))
		if buildings[0] == 1:
			buildings[0] = 2
			if length > 1:
				if buildings[1] == 0:
					buildings[1] = 2
		for i in range(1, length - 1):
			if buildings[i] == 1:
				buildings[i] = 2
				if buildings[i + 1] == 0:
					buildings[i + 1] = 2
				if buildings[i - 1] == 0:
					buildings[i - 1] = 2
		if buildings[length - 1] == 1:
			buildings[length - 1] = 2
			if buildings[length - 2] == 0:
				buildings[length - 2] = 2
		print(buildings.count(0))
	else:
		print(0)
	inputs = inputs - 1


def not_destroyed(x, n):
	for j in range(n):
		if x[j] == '1':
			x[j] = '2'
			if j - 1 >= 0:
				x[j - 1] = '2'
			if j + 1 < n and x[j + 1] != '1':
				x[j + 1] = '2'
	return x.count('0')
T = int(input())
for i in range(T):
	L = []
	N = int(input())
	S = input()
	for j in range(N):
		L.append(S[j])
	n = not_destroyed(L, N)
	print(n)


def main():
	T = int(input())
	for test in range(T):
		N = int(input())
		buildingList = input().strip()
		totalStanding = N
		for (index, building) in enumerate(buildingList):
			if building == '1' or (index > 0 and buildingList[index - 1] == '1') or (index < N - 1 and buildingList[index + 1] == '1'):
				totalStanding -= 1
		print(totalStanding)

def __starting_point():
	main()
__starting_point()


t = int(input())
for nTest in range(t):
	n = int(input())
	s = input().strip()
	ns = int(s)
	ns = ns + ns // 10 + 10 * ns
	ss = str(ns)[-n:]
	print(ss.count('0') + n - len(ss))


t = int(input())
for nTest in range(t):
	n = int(input())
	s = list(input().strip())
	answer = 0
	for i in range(n):
		if (i == 0 or s[i - 1] == '0') and s[i] == '0' and (i == n - 1 or s[i + 1] == '0'):
			answer += 1
	print(answer)


cases = int(input())
for case in range(cases):
	length = int(input())
	buildings = [1] * length
	bombs = input()
	for i in range(length):
		if bombs[i] == '1':
			buildings[i] = 0
			if i != 0:
				buildings[i - 1] = 0
			if i != length - 1:
				buildings[i + 1] = 0
			i = i + 2
	print(buildings.count(1))


x = int(input())
listk = []
for i in range(0, x):
	len_s = int(input())
	build = input()
	list1 = []
	for e in build:
		list1.append(e)
	for i in range(0, len_s):
		if list1[i] == '1':
			list1[i] == 'R'
			if i - 1 >= 0:
				list1[i - 1] = 'R'
			if i != len_s - 1:
				if list1[i + 1]:
					if list1[i + 1] != '1':
						list1[i + 1] = 'R'
	sum = 0
	for e in list1:
		if e == '0':
			sum = sum + 1
	listk.append(sum)
for e in listk:
	print(e)


def main():
	T = int(input())
	for i in range(T):
		N = int(input())
		S = input()
		R = {}
		for i in range(N):
			if S[i] == '1':
				R[i - 1] = 2
				R[i] = 2
				R[i + 1] = 2
		R[-1] = 0
		R[N] = 0
		print(N - list(R.values()).count(2))

def __starting_point():
	main()
__starting_point()


def process(N, S):
	C = 0
	for i in range(1, N + 1):
		if S[i - 1] or S[i] or S[i + 1]:
			C += 1
	return N - C

def main():
	T = int(input().strip())
	for t in range(T):
		N = int(input().strip())
		S = [0] + list(map(int, input().strip())) + [0]
		print(process(N, S))
main()


N = int(input())
for i in range(0, N):
	inp = int(input())
	inpu = input()
	input_list = []
	for j in range(0, inp):
		input_list += [inpu[j]]
	li = []
	if input_list[0] == '1':
		li += [0, 1]
	if input_list[inp - 1] == '1':
		li += [inp - 1, inp - 2]
	for k in range(1, inp - 1):
		if input_list[k] == '1':
			li += [k - 1, k, k + 1]
	li = list(set(li))
	t = inp - len(li)
	if t < 0:
		print('0')
	else:
		print(t)


t = int(input())
for i in range(t):
	N = int(input())
	word = input()
	hit = [0] * N
	for x in range(N):
		if word[x] == '1':
			hit[x] = 1
			if x > 0:
				hit[x - 1] = 1
			if x < N - 1:
				hit[x + 1] = 1
	print(hit.count(0))


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