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: interview

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()

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(raw_input().strip())
 s = input().strip()
 ns = int(s) + int(s[1:]+'0') + int('0'+s[:-1])
 ss = str(ns)
 print(ss.count("0") + len(s)-len(ss))
##    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


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()

#!/usr/bin/env python

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


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)