Chef has to work on a project for the next N hours. He is given a work plan to do this, which is given to you as a binary string S of length N. S_{i} = 1 if Chef has to work on the project during the i-th hour, and S_{i} = 0 if Chef is free during the i-th hour.

Chef would like to use some of his free time to take naps. He needs a minimum of K consecutive hours of free time to take a nap. What is the maximum number of naps that Chef can take during the next N hours?

Note that it is allowed for one nap to immediately follow another, i.e, Chef can wake up from one nap and then immediately take another one (if he has enough free time to do so), and these will be counted as different naps.

------ Input Format ------ 

- The first line of 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 two space-separated integers N and K respectively.
- The second line of each test case contains a binary string S of length N denoting Chef's work plan.

------ Output Format ------ 

- For each test case, print a single line containing one integer — the maximum number of naps that Chef can take.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
- Sum of $N$ over all test cases doesn't exceed $2 \cdot 10^{5}$
$S$ is a binary string, i.e, each character of $S$ is either 0 or 1.

----- Sample Input 1 ------ 
3
4 1
1010
4 2
0100
11 3
00100000001
----- Sample Output 1 ------ 
2
1
2
----- explanation 1 ------ 
Test Case 1: Chef can take two naps starting from the $2^{nd}$ and $4^{th}$ hours respectively.

Test Case 2: Chef can take a nap starting from the $3^{rd}$ hour.

Test Case 3: Chef can take one nap starting from the $5^{th}$ hour and another starting from the $8^{th}$ hour.

Difficulty: MEDIUM
Tags: String algorithms

Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	c = 0
	for i in s:
		if i == '0':
			c += 1
		else:
			c = 0
		if c == k:
			c = 0
			count += 1
	print(count)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	a = input() + '1'
	cur = 0
	ans = 0
	for i in a:
		if i == '1':
			ans += cur // k
			cur = 0
		else:
			cur += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	maxnap = 0
	count = 0
	for i in s:
		if i == '0':
			count = count + 1
		else:
			if count >= k:
				maxnap = maxnap + count // k
			count = 0
	if count == k:
		maxnap = maxnap + 1
	print(maxnap)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	hours = input()
	print(hours.count('0' * k))


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	b = input()
	(s, e) = (0, 0)
	z = 0
	naps = 0
	while e < n:
		if b[e] == '1':
			naps += z // k
			s = e
			z = 0
		else:
			z += 1
		e += 1
	if z:
		naps += z // k
	print(naps)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = str(input())
	print(l.count(k * '0'))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = input()
	ans = 0
	c = 0
	for i in l:
		if i == '1':
			ans += c // k
			c = 0
		else:
			c += 1
	if c:
		ans += c // k
	print(ans)


t = int(input())
n = []
k = []
s = []
naps = []
for i in range(t):
	(_n, _k) = input().split()
	n.append(_n)
	k.append(_k)
	_s = input()
	s.append(_s)
for i in range(t):
	sec = []
	breaks = 0
	for bit in s[i]:
		if bit == '0':
			breaks += 1
		if bit == '1':
			sec.append(breaks)
			breaks = 0
	sec.append(breaks)
	max_naps = 0
	for hr in sec:
		max_naps += hr // int(k[i])
	print(max_naps)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	c = 0
	count = 0
	for i in range(n):
		if s[i] == '0':
			c += 1
		if s[i] == '1':
			c = 0
		if c == m:
			c = 0
			count += 1
	print(count)


t = 1
io = t - 2
k = int(input())
for i in range(k):
	(a, b) = map(int, input().split())
	s = input()
	sum = 0
	c = 0
	for i in range(a):
		if s[i] == '0':
			sum += 1
		if s[i] == '1':
			sum = 0
		if sum == b:
			sum = 0
			c += 1
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	x = 0
	l = []
	for i in range(n):
		if s[i] == '0':
			x += 1
		else:
			l.append(x)
			x = 0
	l.append(x)
	m = [j // k for j in l]
	print(sum(m))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	m = 1
	res = 0
	i = 0
	if k == 1:
		for i in s:
			if i == '0':
				res += 1
		print(res)
		res = 0
		continue
	while i < len(s) - 1:
		if s[i] == '0' and s[i + 1] == '0':
			m += 1
		else:
			m = 1
		if m == k:
			res += 1
			m = 1
			i += 1
		i += 1
	print(res)


for _ in range(int(input())):
	(N, K) = map(int, input().split(' '))
	s = input()
	count = 0
	c = 0
	for i in s:
		if i == '0':
			c += 1
		if i == '1':
			c = 0
		if c == K:
			c = 0
			count += 1
	print(count)


def strings(s, n, k):
	i = 0
	count = 0
	while i < n:
		if s[i] == '0':
			cons = 0
			while s[i] == '0':
				cons += 1
				i += 1
				if cons == k:
					count += 1
					cons = 0
				if i == n:
					break
		else:
			i += 1
	print(count)
for i in range(int(input())):
	(l, k) = [int(x) for x in input().split()]
	s = input()
	strings(s, l, k)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s = list(s)
	count = 0
	c = 0
	for x in range(n):
		if s[x] == '0':
			c += 1
		if s[x] == '1':
			c = 0
		if c == k:
			count += 1
			c = 0
	print(count)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	count = 0
	final = 0
	for i in S:
		if i == '0':
			count += 1
			if count == K:
				final += 1
				count = 0
		else:
			count = 0
	print(final)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	s = input()
	i = 0
	c = 0
	while i <= n - k:
		if k * '0' == s[i:i + k]:
			i += k
			c += 1
		else:
			i += 1
	print(c)
	t -= 1


import re
x = int(input())
fg = []
for un in range(0, x):
	lp = str(input())
	kr = lp.split(' ')
	ynm = []
	for vcx in kr:
		ynm.append(int(vcx))
	pl = str(input())
	ynm.append(pl)
	fg.append(ynm)
for klew in fg:
	jkl = klew[1]
	the = re.findall('0+', klew[2])
	mpt = 0
	for bbh in the:
		if len(bbh) < jkl:
			continue
		elif len(bbh) == jkl:
			mpt += 1
		else:
			mpt += len(bbh) // jkl
	print(mpt)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	s = input()
	v = k * '0'
	c = 0
	while v in s:
		s = s.replace(v, '', 1)
		c += 1
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	d = 0
	for i in range(n):
		if c == k:
			d += 1
			c = 0
		if s[i] == '0':
			c += 1
		else:
			c = 0
	if c == k:
		d += 1
	print(d)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	z = 0
	cnt = 0
	for i in range(n):
		if s[i] == '0':
			z += 1
			if z == k:
				cnt += 1
				z = 0
		else:
			z = 0
	print(cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(count, temp) = (0, 0)
	for i in range(n):
		if s[i] == '0':
			temp += 1
			if temp == k:
				count += 1
				temp = 0
		else:
			temp = 0
	print(count)


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	s = input()
	ch = 0
	naps = 0
	for j in range(n):
		if s[j] == '0':
			ch += 1
			if ch == k:
				naps += 1
				ch = 0
		else:
			ch = 0
	print(naps)


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


for i in range(int(input())):
	(N, K) = map(int, input().split(' '))
	lis = str(input())
	s = 0
	n = 0
	for j in range(N):
		if lis[j] == '0':
			s += 1
			if s == K:
				n += 1
				s = 0
		else:
			s = 0
	print(n)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().split('1')
	lk = [len(i) // k for i in s]
	print(sum(lk))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	s.append('1')
	c = 0
	x = []
	for i in s:
		if i == '0':
			c += 1
		else:
			x.append(c)
			c = 0
	xx = [i // k for i in x]
	print(sum(xx))


import re
for i in range(int(input())):
	(n, k) = map(int, input().split())
	string = input()
	pattern = '1*0+1*'
	list = re.findall(pattern, string)
	sum1 = 0
	for i in list:
		list2 = [j for j in i]
		g = list2.count('0')
		sum1 = sum1 + g // k
	print(sum1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	lis = []
	x = s.split('1')
	for i in range(len(x)):
		if len(x[i]) >= k:
			lis.append(int(len(x[i]) / k))
	if len(lis) == 0:
		print(0)
	else:
		print(sum(lis))


t = int(input())
for i in range(0, t):
	nk = input().split()
	n = int(nk[0])
	k = int(nk[1])
	s = str(input())
	j = 0
	count = 0
	while j <= n - k:
		maximum = int(s[j:j + k])
		if maximum == 0:
			count = count + 1
			j = j + k
		else:
			j = j + 1
	print(count)


T = int(input())
for i in range(T):
	(x, y) = map(int, input().split())
	s = input()
	q = list(map(len, s.split('1')))
	count = 0
	for i in q:
		if y == i:
			count += 1
		elif i > y:
			count += int(i // y)
	print(count)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input().split('1'))
	nap = 0
	for ele in s:
		if len(ele) >= k:
			nap += len(ele) // k
	print(nap)


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	s = input()
	a = s.count(k * '0')
	print(a)


t = int(input())
while t > 0:
	(N, K) = map(int, input().split())
	S = str(input())
	count = 0
	c = 0
	for i in S:
		if i == '0':
			c = c + 1
		else:
			c = 0
		if c == K:
			c = 0
			count = count + 1
	print(count)
	t = t - 1


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	ans = s.count(k * '0')
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	cnt = 0
	find = k * '0'
	while find in s:
		s = s.replace(find, '', 1)
		cnt += 1
	print(cnt)


s = int(input())
for i in range(s):
	(n, k) = map(int, input().split())
	a = input()
	ans = a.count(k * '0')
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	d = '0' * k
	print(s.count(d))


for _ in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	print(input().count('0' * K))


import sys
input = sys.stdin.readline

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

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

def insr():
	return input().strip()

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	(N, K) = inlt()
	ans.append(insr().count('0' * K))
outplt(ans)


import sys
input = sys.stdin.readline

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

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

def insr():
	return input().strip()

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	(N, K) = inlt()
	S = insr()
	an = 0
	t = 0
	for s in S:
		if s == '1':
			t = 0
		else:
			t += 1
			if t == K:
				an += 1
				t = 0
	ans.append(an)
outplt(ans)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	s = input()
	curr = 0
	ans = 0
	for i in s:
		if i == '0':
			curr += 1
		else:
			curr = 0
		if curr == k:
			ans += 1
			curr = 0
	print(ans)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	st = input()
	t = 0
	n = 0
	for j in st:
		if j == '1':
			t = 0
		else:
			t += 1
		if t == b:
			n += 1
			t = 0
	print(n)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = input().split('1')
	c = 0
	for i in a:
		if len(i) >= k:
			c += len(i) // k
	print(c)


for _ in range(int(input())):
	(b, c) = map(int, input().split())
	d = input()
	s = 0
	i = 0
	k = 0
	if c == 1:
		k = d.count('0')
	else:
		while s < b:
			if '0' in d[s:s + c] and len(set(d[s:s + c])) == 1 and (d[s:s + c].count('0') == c):
				k = k + 1
				s = s + c
			else:
				s = s + 1
	print(k)


for x in range(int(input())):
	(n, k) = [int(d) for d in input().split()]
	a = input()
	final = 0
	count = 0
	for i in range(n):
		if a[i] == '0':
			count += 1
		else:
			count = 0
		if count == k:
			final += 1
			count = 0
	print(final)


T = int(input())
for _ in range(T):
	(N, K) = list(map(int, input().split()))
	S = input()
	cnt = 0
	s_cnt = 0
	for i in S:
		if int(i) == 0:
			cnt += 1
			if cnt == K:
				s_cnt += 1
				cnt = 0
		else:
			cnt = 0
	print(s_cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	inp = input()
	cnt = 0
	ans = 0
	if k == 1:
		ans = inp.count('0')
	else:
		for i in inp:
			if i == '0':
				cnt += 1
			else:
				cnt = 0
			if cnt == k:
				ans += 1
				cnt = 0
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = input()
	temp = 0
	ans = 0
	for i in arr:
		if i == '0':
			temp += 1
		else:
			ans += temp // k
			temp = 0
	ans += temp // k
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	a = []
	a[0:] = s
	count = 0
	naps = 0
	for i in a:
		if i == '0':
			count = count + 1
			if count == k:
				naps = naps + 1
				count = 0
		else:
			count = 0
	print(naps)


for _ in range(int(input())):
	(n, t) = map(int, input().split())
	s = input()
	(a, temp) = (0, 0)
	for i in range(n):
		if int(s[i]) == 0:
			temp += 1
		else:
			temp = 0
		if temp == t:
			a += 1
			temp = 0
	print(a)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = input() + '1'
	zero_seq = 0
	ans = 0
	for x in S:
		if x == '0':
			zero_seq += 1
		else:
			ans += zero_seq // K
			zero_seq = 0
	print(ans)


t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	s = input()
	count = 0
	mc = 0
	tc = 0
	for i in s:
		if i == '0':
			count += 1
			if count >= mc:
				mc = count
				if mc >= m:
					tc += 1
					count = 0
		else:
			count = 0
	print(tc)


tst = int(input())
for i in range(tst):
	(num, k) = map(int, input().split())
	st = input()
	li = ''
	check = ''
	c = 0
	for j in range(k):
		li = li + '0'
	for j in range(num):
		check = check + str(st[j])
		if li in check:
			c = c + 1
			check = ''
	print(c)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	main_list = []
	count1 = 0
	count2 = 0
	for i in s:
		if i == '0':
			count1 += 1
		else:
			if count1 != 0:
				main_list.append(count1)
			count1 = 0
	if count1 != 0:
		main_list.append(count1)
	for i in main_list:
		count2 += i // k
	print(count2)


def sleepychef(n, k, s):
	a = 0
	b = 0
	for j in range(n):
		if s[j] == '0':
			a += 1
			if a == k:
				b += 1
				a = 0
		else:
			a = 0
	return b
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	print(sleepychef(n, k, s))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	a = 0
	b = 0
	for i in range(n):
		if s[i] == '0':
			a += 1
			if a == k:
				b += 1
				a = 0
		else:
			a = 0
	print(b)


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	S = input()
	sm = 0
	knt = 0
	for i in range(len(S)):
		if S[i] == '0':
			sm += 1
			if sm == K:
				knt += 1
				sm = 0
		else:
			sm = 0
	print(knt)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	arr = []
	c = 0
	for i in s:
		if i == '0':
			c += 1
		else:
			arr.append(c)
			c = 0
	arr.append(c)
	for i in range(len(arr)):
		arr[i] = arr[i] // k
	print(sum(arr))