Read problem statements in [Mandarin Chinese] and [Bengali].

There are N positions in a queue. Given a *binary string* S of length N, where S_{i} = '1' denotes, there is a person standing in the i^{th} position.

The distance between two people standing in the i^{th} and j^{th} positions respectively in the queue is \mid i - j \mid, where \mid x \mid denotes the absolute value of x. Now, two people are considered to be friends if they are at a distance less than or equal to K. 

Let's say, there are M people, P_{1}, P_{2}, \dots, P_{M} standing one after another in a queue such that for each 1 ≤ i < M, P_{i} and P_{i+1} are friends, then all the M people are considered to be in a *friend group*.

For example, consider the string S = "1101001" and K = 2. 

Let's denote the people standing in the 1^{st}, 2^{nd}, 4^{th} and 7^{th} positions in the queue by P_{1}, P_{2}, P_{3}, P_{4} respectively. Now, P_{1} and P_{2} are friends as the distance between them is 1, P_{2} and P_{3} are also friends as the distance between them is 2. P_{4} is not friend with anyone. Hence P_{1}, P_{2}, P_{3} form a friend group and P_{4} forms a separate friend group.

Now each person can move one position right or one position left or stay in the same position. However, they can't move out of the queue. Find the *minimum* number of friend groups they can form if they move optimally.

It is possible that there is more than one person standing in the same position after the movements.

------ 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 integers N, K.
- The second line of each test case contains a string S.

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

For each test case, print a single line containing one integer - the minimum number of friend groups.

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

$1 ≤ T ≤ 5\cdot10^{4}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ K ≤ N$
$S$ contains only characters '$0$ and '$1$'
- The sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
3
6 2
010010
4 0
1001
7 2
1101001

----- Sample Output 1 ------ 
1
2
1
----- explanation 1 ------ 
- Test case $1$: If the person standing in the $5^{th}$ position moves one position left, the distance between the two people becomes $2$ which is equal to $K$. So they form a friend group.

- Test case $2$: If the person standing in the $1^{st}$ position moves one position right and the person standing in the $4^{th}$ position moves one position left, the string becomes "$0110$", still the distance between them is greater than $K = 0$. So they form two separate friend groups.

- Test case $3$: Initially first three people form a friend group and the fourth person forms a separate friend group. Now if the fourth person moves one position left, he becomes a friend of the third person as the distance between these two people is equal to $2$, and hence all the four people belong to one friend group.

Difficulty: VERY_HARD
Tags: String algorithms

Dynamic programming

Data structures

Greedy algorithms
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	if '1' not in s:
		print(0)
	else:
		c = 1
		r = s.index('1') + 1
		for j in range(n):
			if s[j] == '1':
				if j == r + k:
					r = j
				elif j < r + k:
					r = j + 1
				elif j == r + k + 1:
					r = j - 1
				else:
					c += 1
					r = j + 1
		print(c)


def solution(n, k, S):
	if '1' not in S:
		return 0
	groupCount = 1
	rightMostFriendIndex = S.index('1') + 1
	for i in range(n):
		if S[i] == '1':
			if i == rightMostFriendIndex + k:
				rightMostFriendIndex = i
			elif i < rightMostFriendIndex + k:
				rightMostFriendIndex = i + 1
			elif i == rightMostFriendIndex + k + 1:
				rightMostFriendIndex = i - 1
			else:
				groupCount += 1
				rightMostFriendIndex = i + 1
	return groupCount
t = int(input())
for _ in range(t):
	inputs = [int(item) for item in input().split()]
	n = inputs[0]
	k = inputs[1]
	S = input()
	print(solution(n, k, S))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	p = -1000000.0
	ans = 0
	for i in range(len(s)):
		if s[i] == '0':
			continue
		if i - p <= k + 1:
			p = min(i + 1, p + k)
		else:
			ans += 1
			p = i + 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	(ans, last) = (0, -10 ** 9)
	for i in range(len(s)):
		if s[i] == '1':
			if i - last <= k + 1:
				last = min(last + k, i + 1)
			else:
				last = i + 1
				ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	last = -99999
	for x in range(n):
		if s[x] == '1':
			if x - last <= k + 1:
				last = min(last + k, x + 1)
			else:
				ans += 1
				last = x + 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	low = -1
	count = 1
	if s.count('1') == 0:
		print(0)
	else:
		j = 0
		while j < n:
			if s[j] == '1':
				if low == -1:
					low = j + 1
				elif j - low < k:
					low = j + 1
				elif j - low == k:
					low = j
				elif j - low == k + 1:
					low = j - 1
				elif j - low > k + 1:
					low = j + 1
					count += 1
			j += 1
		print(count)


T = int(input())
for t in range(T):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	found = False
	tot = 0
	for i in range(n):
		if s[i] == '1':
			if found == False:
				latest = i + 1
				tot = 1
				found = True
			elif i - latest < k:
				latest = i + 1
			elif i - latest == k:
				latest = i
			elif i - latest == k + 1:
				latest = i - 1
			else:
				latest = i + 1
				tot += 1
	print(tot)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = []
	for i in range(n):
		if s[i] == '1':
			l.append(i + 1)
	n = len(l)
	ans = 1
	prev = -1
	for i in range(n):
		if prev == -1:
			l[i] += 1
			prev = l[i]
		elif l[i] - prev < k:
			l[i] += 1
			prev = l[i]
		elif l[i] - prev == k:
			prev = l[i]
		elif l[i] - prev > k:
			if l[i] - prev - k == 1:
				l[i] -= 1
				prev = l[i]
			else:
				l[i] += 1
				prev = l[i]
				ans += 1
	if not l:
		print(0)
	else:
		print(ans)


def solveD():
	for i in range(len(S)):
		if i == 0:
			if S[i] < N:
				S[i] += 1
		elif S[i] - S[i - 1] == K + 1:
			S[i] -= 1
		elif S[i] - S[i - 1] < K and S[i] < N or (S[i] - S[i - 1] > K and S[i] < N):
			S[i] += 1
	if not K:
		return len(set(S))
	ans = 0
	friends = True
	for i in range(len(S) - 1):
		if friends:
			if S[i + 1] - S[i] <= K:
				continue
			else:
				friends = False
				ans += 1
		elif S[i + 1] - S[i] > K:
			ans += 1
			continue
		else:
			friends = True
	if len(S):
		ans += 1
	return ans
for _ in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	S = [i for (i, x) in enumerate(input()) if x == '1']
	print(solveD())


t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	s = input()
	prev = -1000000007
	gps = 0
	for i in range(n):
		if s[i] == '0':
			continue
		if i - prev <= k + 1:
			prev = min(k + prev, i + 1)
		else:
			gps += 1
			prev = i + 1
	print(gps)


t = int(input())
for z in range(0, t):
	(n, k) = map(int, input().split())
	arr = input()
	prev1 = -5
	dist = 0
	count = 0
	for i in range(0, n):
		if arr[i] == '1':
			if count == 0:
				count += 1
				prev1 = i + 1
			else:
				dist = abs(prev1 - i)
				if dist < k:
					prev1 = i + 1
				elif dist == k:
					prev1 = i
				elif dist == k + 1:
					prev1 = i - 1
				else:
					count += 1
					prev1 = i + 1
	print(count)


import sys
input = lambda : sys.stdin.readline()
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	last = -10 ** 6
	for i in range(n):
		if s[i] == '0':
			continue
		if i - last <= k + 1:
			last = min(last + k, i + 1)
		else:
			ans += 1
			last = i + 1
	print(ans)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	res = 0
	last = -math.inf
	for i in range(n):
		if s[i] == '0':
			continue
		if i - last <= k + 1:
			last = min(last + k, i + 1)
		else:
			res += 1
			last = i + 1
	print(res)


t = int(input())
for i in range(t):
	ans = 0
	(n, k) = map(int, input().split())
	str = input()
	last = -float('inf')
	for i in range(0, len(str)):
		if str[i] == '1':
			if i - last <= k + 1:
				if i - last == k + 1:
					last = i - 1
				elif i - last == k:
					last = i
				else:
					last = i + 1
			else:
				ans += 1
				last = i + 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = [int(x) for x in input()]
	indices = []
	last = -1
	ans = 0
	for x in range(len(s)):
		if s[x] == 0:
			continue
		if last == -1:
			last = x + 1
			ans += 1
			continue
		if x - last < k:
			last = x + 1
		elif x - last == k:
			last = x
		elif x - last == k + 1:
			last = x - 1
		else:
			if x + 1 - last > k:
				ans += 1
			last = x + 1
	print(ans)


for m in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = input()
	s = list(a)
	power = 0
	group = 0
	pre = 0
	for i in range(n):
		if not group and s[i] == '1':
			pre = i + 1
			power = k + 1
			group += 1
		elif s[i] == '1':
			if abs(pre - (i + 1)) <= power:
				if abs(pre - (i + 1)) == power:
					pre = i + 1
					power = k
				else:
					pre = i + 1
					power = k + 1
			elif abs(pre - (i + 1)) > power:
				if abs(pre - (i + 1)) == power + 1:
					pre = i + 1
					power = k - 1
				else:
					pre = i + 1
					power = k + 1
					group += 1
	print(group)


for t in range(int(input())):
	(n, k) = list(map(int, input().strip().split()))
	s = input()
	i = 0
	last = -1
	c = 0
	while i < n:
		if s[i] == '1':
			if last == -1:
				c += 1
				last = i + 1
			elif i - last <= k + 1:
				last = min(last + k, i + 1)
			else:
				c += 1
				last = i + 1
		i += 1
	print(c)


def solve(n, k, s):
	ans = [i for i in range(n) if s[i] == '1']
	if ans == []:
		print(0)
		return
	c = 1
	ans[0] += 1
	for i in range(1, len(ans)):
		if abs(ans[i] + 1 - ans[i - 1]) <= k:
			ans[i] += 1
		elif abs(ans[i] - ans[i - 1]) <= k:
			pass
		elif abs(ans[i] - 1 - ans[i - 1]) <= k:
			ans[i] -= 1
		else:
			ans[i] += 1
			c += 1
	print(c)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	solve(n, k, s)


import math
from bisect import bisect_left
import collections

def combination(n, r):
	return math.comb(n, r)

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

def intp():
	return int(input())

def inp():
	return input()

def inpspl():
	return input().split()

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

def sqrt(n):
	return math.sqrt(n)

def gcd(a, b):
	return math.gcd(a, b)

def lcm(a, b):
	return a * b // gcd(a, b)

def p(s):
	print(f'{s}')

def lsetl(lst):
	return list(set(lst))

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(abs(n - r))

def frequencyofall(lst):
	dict(collections.Counter(lst))

def ispowerof2(n):
	return n & n - 1 == 0

def dictionarysort(d):
	return collections.OrderedDict(sorted(d.items()))

def solve():
	for _ in range(intp()):
		(n, k) = mapping()
		s = inp()
		if s.count('1') == 0:
			p(0)
		else:
			ans = 0
			last = -1 * (10 ** 9 + 7)
			for i in range(len(s)):
				if s[i] == '1':
					if i - last <= k + 1:
						last = min(last + k, i + 1)
					else:
						ans += 1
						last = i + 1
			p(ans)
solve()


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	last = -1000000
	for i in range(n):
		if s[i] == '1':
			if i - last <= k + 1:
				last = min(last + k, i + 1)
			else:
				ans += 1
				last = i + 1
	print(ans)
	t -= 1


def solve():
	(n, k) = [int(x) for x in input().split(' ')]
	s = input()
	s = list(s)
	prev = -1
	ans = 0
	for i in range(n):
		if s[i] == '0':
			continue
		if prev == -1:
			prev = i + 1
			ans = 1
			continue
		if i - prev == k:
			prev = i
		elif i - prev == k + 1:
			prev = i - 1
		else:
			if i + 1 - prev > k:
				ans += 1
			prev = i + 1
	print(ans)
	return
t = int(input())
for i in range(t):
	solve()


import sys
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	groups = 0
	last = -sys.maxsize
	for i in range(n):
		if s[i] == '0':
			continue
		if i - last <= k + 1:
			last = min(last + k, i + 1)
		else:
			groups += 1
			last = i + 1
	print(groups)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	ans = 0
	last = -99999999
	for i in range(len(S)):
		if S[i] == '0':
			continue
		if i - last <= K + 1:
			last = min(last + K, i + 1)
		else:
			ans += 1
			last = i + 1
	print(ans)


for i in range(int(input())):
	linput = tuple(map(int, input().split()))
	(N, K) = linput
	linput = input()
	fandgrp = 0
	lastperson = 0 - K - 10
	for j in range(N):
		if int(linput[j]) == 1:
			if not abs(j - lastperson) <= K + 1:
				fandgrp += 1
				lastperson = j + 1
			else:
				lastperson = min(K + lastperson, j + 1)
	print(fandgrp)


for T in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	pre = -10 ** 6
	ans = 0
	for i in range(n):
		if s[i] == '0':
			continue
		distance = i - pre
		if distance <= k + 1:
			if distance == k:
				pre = i
			elif distance < k:
				pre = i + 1
			else:
				pre = i - 1
		else:
			ans += 1
			pre = i + 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	groups = 0
	prev = -1
	i = 0
	while i < n:
		if s[i] == '1':
			if prev == -1:
				prev = i + 1
				groups += 1
			elif i - prev < k:
				prev = i + 1
			elif i - prev == k:
				prev = i
			elif i - prev == k + 1:
				prev = i - 1
			else:
				prev = i + 1
				groups += 1
		i += 1
	print(groups)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	string = input()
	grp = 0
	last = -1000000.0
	for idx in range(n):
		if string[idx] == '0':
			continue
		if idx - last <= k + 1:
			last = min(last + k, idx + 1)
		else:
			grp += 1
			last = idx + 1
	print(grp)
	t = t - 1


t = int(input())

def same(lst, val):
	return [i for (i, x) in enumerate(lst) if x == val]
for _ in range(t):
	out = 0
	last = -1000000
	(n, k) = map(int, input().split())
	s = str(input())
	pos = same(s, '1')
	for x in pos:
		if x - last <= k + 1:
			last = min(last + k, x + 1)
		else:
			out += 1
			last = x + 1
	print(out)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input()
	last_person_idx = -1
	dist = []
	for i in range(len(s)):
		if s[i] == '1':
			if last_person_idx != -1:
				dist.append(i - last_person_idx)
			last_person_idx = i
	if last_person_idx == -1:
		print(0)
		t = t - 1
		continue
	ans = 1
	dist.append(1000000)
	dist[0] = dist[0] - 1
	for i in range(1, len(dist)):
		if dist[i - 1] == k + 1:
			dist[i] = dist[i] + 1
		else:
			if dist[i - 1] > k + 1:
				ans = ans + 1
			if dist[i - 1] != k:
				dist[i] = dist[i] - 1
	print(ans)
	t = t - 1


T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	s = input()
	last = -1
	ans = 0
	for i in range(n):
		if s[i] == '1':
			if last == -1:
				last = i + 1
				ans += 1
			elif i - last < k:
				last = i + 1
			elif i - last == k:
				last = i
			elif i - last == k + 1:
				last = i - 1
			elif i - last > k + 1:
				last = i + 1
				ans += 1
	print(ans)


import sys
input = lambda : sys.stdin.readline()
int_arr = lambda : list(map(int, input().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().split())
get_int = lambda : map(int, input().split())
get_flo = lambda : map(float, input().split())
mod = 1000000007

def solve(n, k, s):
	ans = [i for i in range(n) if s[i] == '1']
	if ans == []:
		print(0)
		return
	c = 1
	ans[0] += 1
	for i in range(1, len(ans)):
		if abs(ans[i] + 1 - ans[i - 1]) <= k:
			ans[i] += 1
		elif abs(ans[i] - ans[i - 1]) <= k:
			pass
		elif abs(ans[i] - 1 - ans[i - 1]) <= k:
			ans[i] -= 1
		else:
			ans[i] += 1
			c += 1
	print(c)
for _ in range(int(input())):
	(n, k) = get_int()
	s = str(input())[:-1]
	solve(n, k, s)


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = list(input())
	y = -1
	if a.count('1') == 0:
		print(0)
	else:
		c = 1
		for i in range(n):
			if a[i] == '1':
				if y == -1:
					y = i + 1
				elif i - y > k:
					if i - 1 - y <= k:
						y = i - 1
					else:
						c += 1
						y = i + 1
				elif i - y < k:
					y = i + 1
				else:
					y = i
		print(c)
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	last = -1000000
	ans = 0
	for i in range(n):
		if s[i] == '0':
			continue
		if i - last <= k + 1:
			last = min(last + k, i + 1)
		else:
			ans += 1
			last = i + 1
	print(ans)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
sys.setrecursionlimit(depth)
from math import inf, ceil
from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	(last, ans) = (-1, 0)
	for i in range(n):
		if s[i] == '0':
			continue
		if last == -1:
			(last, ans) = (i + 1, 1)
			continue
		if i - last == k:
			last = i
		elif i - last == k + 1:
			last = i - 1
		else:
			if i - last > k + 1:
				ans += 1
			last = i + 1
	print(ans)


def prog_name():
	(n, k) = map(int, input().split())
	s = input()
	s = list(s)
	l = -9999999
	cnt = 0
	for x in range(n):
		if s[x] == '1':
			if abs(x - l) <= k + 1:
				l = min(l + k, x + 1)
			else:
				cnt += 1
				l = x + 1
	print(cnt)
T = int(input())
for unique in range(T):
	prog_name()


from collections import defaultdict
from itertools import permutations
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(10 ** 6)
input = stdin.readline
cout = stdout.write
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	last = 0
	ans = 0
	for i in range(n):
		if s[i] == '1':
			last = i + 1
			ans = 1
			break
	st = last
	for i in range(st, n):
		if s[i] == '1':
			dist = i - last
			if dist == k:
				last = i
			elif dist == k + 1:
				last = i - 1
			elif dist < k:
				last = i + 1
			elif dist > k + 1:
				ans += 1
				last = i + 1
	print(ans)


def sol(s, n, k):
	last = float('-inf')
	res = 0
	for i in range(n):
		if s[i] == '0':
			continue
		if i - last <= k + 1:
			last = min(last + k, i + 1)
		else:
			last = i + 1
			res += 1
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(sol(s, n, k))


t = int(input())
while t:
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	l = -1000000.0
	for i in range(0, len(s)):
		if s[i] == '0':
			continue
		elif i - l <= k + 1:
			l = min(k + l, i + 1)
		else:
			ans = ans + 1
			l = i + 1
	print(ans)
	t = t - 1


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = 0
	l = -1000000000.0
	for i in range(n):
		if s[i] == '0':
			continue
		if i - l <= k + 1:
			l = min(l + k, i + 1)
		else:
			a += 1
			l = i + 1
	print(a)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	prevIndex = float('-inf')
	for (index, char) in enumerate(s):
		if char == '1':
			if index - prevIndex <= k + 1:
				prevIndex = min(prevIndex + k, index + 1)
			else:
				prevIndex = index + 1
				count += 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	prev = -10 ** 9
	ans = 0
	for i in range(n):
		if s[i] == '1':
			if i - prev <= k + 1:
				prev = min(prev + k, i + 1)
			else:
				ans += 1
				prev = i + 1
	print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	ans = 0
	last = -float('inf')
	for i in range(N):
		if S[i] == '1':
			if i - last <= K + 1:
				last = min(last + K, i + 1)
			else:
				ans += 1
				last = i + 1
	print(ans)


import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	s = input().strip()
	xx = s.count('1')
	if xx == 0:
		print(0)
		continue
	ll = []
	f = 0
	c = 0
	for i in s:
		if i == '1':
			ll.append(c)
		c += 1
	gr = 1
	ll[0] += 1
	for i in range(len(ll) - 1):
		if ll[i + 1] - ll[i] == k:
			continue
		if ll[i + 1] - ll[i] < k:
			ll[i + 1] += 1
			continue
		if ll[i + 1] - ll[i] == k + 1:
			ll[i + 1] -= 1
			continue
		else:
			gr += 1
			ll[i + 1] += 1
	print(gr)


import math
inf = int(10000000000.0 + 7)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	if '1' not in s:
		print(0)
		continue
	index = -1
	g = 0
	for i in range(n):
		if s[i] == '1':
			if index == -1:
				index = i + 1
			elif i - index > k:
				if i - index <= k + 1:
					index = i - 1
				else:
					index = i + 1
					g += 1
			elif i - index < k:
				index = i + 1
			else:
				index = i
	print(g + 1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	mc = -1
	gc = 1
	if s.count('1') == 0:
		print(0)
		continue
	for i in range(n):
		if s[i] == '1':
			if mc == -1:
				mc = i + 1
			elif i - mc > k:
				if i - 1 - mc <= k:
					mc = i - 1
				else:
					gc += 1
					mc = i + 1
			elif i - mc < k:
				mc = i + 1
			else:
				mc = i
	print(gc)


import sys
input = sys.stdin.readline

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

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(n, k) = ma()
	s = st()
	pr = -1
	co = 0
	(lf, rf) = (0, 0)
	for i in range(n):
		if s[i] == '0':
			continue
		elif pr == -1:
			co = 1
			pr = i + 1
			lf = 1
			continue
		else:
			if i - pr == k:
				pr = i
				lf = 1
				continue
			if i - pr < k:
				pr = 1 + i
				lf = 1
				continue
			elif i - pr - 1 == k and lf == 0:
				lf = 1
				pr = i
				continue
			elif i - pr - 1 == k and lf:
				pr = i - 1
				continue
			else:
				co += 1
				pr = i + 1
				lf = 1
	print(co)


from sys import stdin
input = stdin.readline

def answer():
	start = -1
	for i in range(n):
		if s[i] == '1':
			start = i
			break
	if start == -1:
		return 0
	(ans, prev) = (1, start + 1)
	for i in range(start + 1, n):
		if s[i] == '1':
			if i - prev > k + 1:
				ans += 1
				prev = i + 1
			elif i - prev == k + 1:
				prev = i - 1
			elif i - prev < k:
				prev = i + 1
			else:
				prev = i
	return ans
for T in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	print(answer())


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input().strip()
	s = [int(i) for i in s]
	ans = 0
	last = -float('inf')
	move = 0
	for i in range(n):
		if s[i] == 0:
			continue
		else:
			if move and s[i] == 1:
				move = 0
				continue
			move = 0
			if abs(last - i) <= k:
				if abs(i + 1 - last) <= k and i + 1 < n:
					s[i + 1] += 1
					s[i] -= 1
					last = i + 1
					move = 1
				else:
					last = i
			elif abs(i - 1 - last) <= k:
				s[i - 1] += 1
				s[i] -= 1
				last = i - 1
				move = 0
			elif i + 1 < n:
				s[i + 1] += 1
				last = i + 1
				s[i] -= 1
				move = 1
	last = float('inf')
	for i in range(n):
		if s[i]:
			if abs(last - i) > k:
				ans += 1
			last = i
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s = list(s)
	ans = 0
	idx = -1
	for i in range(n):
		if i - idx > k + 1:
			idx = -1
		if s[i] == '1':
			if idx == -1:
				ans += 1
				idx = i + 1
			elif i - idx < k:
				idx = i + 1
			elif i - idx == k + 1:
				idx = i - 1
			elif i - idx == k:
				idx = i
			else:
				idx = i + 1
				ans += 1
	print(ans)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07

def dfs(a, b, p, c):
	if a == b:
		return c
	for (i, j) in adj[a]:
		if i == p:
			continue
		temp = dfs(i, b, a, c + j)
		if dfs(i, b, a):
			mx = max(i, mx)
			return 1
	return tot

def hnbhai(tc):
	(n, k) = sd()
	s = list(sa())
	(tot, strt) = (0, -1)
	abe = 0
	for i in range(n):
		if s[i] == '1':
			if strt != -1:
				if strt > i:
					strt = i + k + 1
				elif strt < i:
					if strt == i - 1:
						strt = i + k - 1
					else:
						strt = i + k + 1
						tot += 1
				else:
					strt = i + k
			else:
				strt = i + k + 1
	print(tot + (s.count('1') > 0))
for _ in range(sb()):
	hnbhai(_ + 1)


cases = int(input())
for _ in range(cases):
	(n, k) = map(int, input().split())
	s = input()
	people = [i for (i, char) in enumerate(s) if char == '1']
	prev_dis = 0
	stack = []
	for p in people:
		if not stack:
			stack.append(p + 1)
		else:
			dif = p - stack[-1]
			if dif < k:
				stack.append(p + 1)
			elif dif == k:
				stack.append(p)
			elif dif == k + 1:
				stack.append(p - 1)
			else:
				stack.append(p + 1)
	if not people:
		ans = 0
	else:
		ans = 1
	ln = len(stack)
	for i in range(1, ln):
		if stack[i] - stack[i - 1] > k:
			ans += 1
	print(ans)


import sys
from bisect import bisect_left as lb
from collections import deque
from queue import PriorityQueue as pq
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
for _ in range(ii()):
	(n, k) = il()
	s = list(ip())
	t = -1
	g = 0
	ans = 0
	for i in range(n):
		if s[i] == '1':
			if t == -1:
				t = i + k + 1
				g = 1
			elif t > i:
				t = i + k + 1
			elif t == i:
				t = i + k
			elif t == i - 1:
				t = i + k - 1
			else:
				t = i + k + 1
				ans += 1
				g = 1
	if g == 1:
		ans += 1
	s1 = s.copy()
	s = s1[::-1]
	t = -1
	g = 0
	ans1 = 0
	for i in range(n):
		if i > t:
			t = -1
			if g == 1:
				ans1 += 1
				g = 0
		if s[i] == '1':
			if t == -1:
				t = i + k + 1
				g = 1
			elif t > i:
				t = i + k + 1
			elif t == i:
				t = i + k
			elif t == i - 1:
				t = i + k - 1
			else:
				t = i + k + 1
				ans += 1
				g = 0
	if g:
		ans1 += 1
	print(min(ans1, ans))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	b = input()
	a = []
	if b.count('1') == 1 or b.count('1') == 0:
		print(b.count('1'))
		continue
	for i in range(n):
		if b[i] == '1':
			a.append(i)
	a[0] += 1
	a[-1] -= 1
	for i in range(1, len(a) - 1):
		if a[i] - a[i - 1] + 1 <= k:
			a[i] += 1
		elif a[i] - a[i - 1] <= k:
			continue
		elif a[i] - 1 - a[i - 1] == k:
			a[i] -= 1
		else:
			a[i] += 1
	ans = 1
	for i in range(1, len(a)):
		if a[i] - a[i - 1] > k:
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	prev = None
	i = 0
	count = 0
	adder = 0
	while i < n:
		if s[i] == '1':
			if prev == None:
				count = count + 1
				adder = 1
				prev = i + 1
			elif i - prev < k:
				prev = i + 1
			elif i - prev == k:
				prev = i
			elif i - prev == k + 1:
				prev = i - 1
			elif i - prev > k + 1:
				count = count + 1
				prev = i + 1
				adder = 0
		i = i + 1
	print(count)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = list(input())
	prev = -1
	dist = []
	for i in range(n):
		if s[i] == '0':
			continue
		if prev == -1:
			prev = i
		else:
			dist.append(i - prev)
			prev = i
	if len(dist) == 0:
		if prev == -1:
			print(0)
		else:
			print(1)
		continue
	c = 0
	prev = -1
	dist[0] -= 1
	for i in range(n):
		if s[i] == '0':
			continue
		if prev == -1:
			prev = i
			continue
		if dist[c] > k:
			if dist[c] - 1 == k:
				dist[c] -= 1
				if c != len(dist) - 1:
					dist[c + 1] += 1
			else:
				dist[c] += 1
				if c != len(dist) - 1:
					dist[c + 1] -= 1
		elif dist[c] < k:
			dist[c] += 1
			if c != len(dist) - 1:
				dist[c + 1] -= 1
		else:
			pass
		c += 1
	c = 1
	for i in dist:
		if i > k:
			c += 1
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(last, count) = (False, 0)
	for (i, c) in enumerate(s):
		if not last and c == '1':
			last = i + 1
		if last:
			if c == '1':
				if i + 1 - k <= last:
					last = i + 1
				elif i - k == last:
					last = i
				elif i - 1 - k == last:
					last = i - 1
				else:
					(last, count) = (i + 1, count + 1)
	print(count if not last else count + 1)


import sys, os, io
input = sys.stdin.readline
PI = 3.141592653589793
INF = float('inf')
MOD = 1000000007

def bin32(num):
	return '{0:032b}'.format(num)

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

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

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]
for t in range(ii()):
	t += 1
	(n, k) = li()
	s = input()
	a = []
	diff = []
	for i in range(n):
		if s[i] == '1':
			a.append(i)
	if len(a) == 0:
		print(0)
		continue
	if len(a) == 1:
		print(1)
		continue
	ans = 1
	a[0] += 1
	a[-1] -= 1
	for i in range(1, len(a)):
		x = a[i] - a[i - 1]
		if x == k:
			continue
		elif x == k + 1:
			if i == len(a) - 1:
				ans += 1
			a[i] -= 1
		else:
			if x > k + 1:
				ans += 1
			a[i] += 1
	print(ans)


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
PI = float('inf')
for _ in range(nmbr()):
	(n, lim) = lst()
	s = input()
	a = [i for i in range(n) if s[i] == '1']
	n = len(a)
	if n == 0:
		print(0)
		continue
	dp = [[PI for i in range(3)] for i in range(n)]
	dp[0][0] = dp[0][1] = dp[0][2] = 1
	for i in range(1, n):
		for j in range(3):
			p2 = a[i] + (j - 1)
			for k in range(3):
				p1 = a[i - 1] + (k - 1)
				if p2 - p1 <= lim:
					dp[i][j] = min(dp[i][j], dp[i - 1][k])
				else:
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + 1)
	print(min(dp[-1]))