A binary string S of length N is called *K-balanced string* if it holds the following property: For each index i\;(1 ≤ i ≤ N) such that S_{i} =  '1', there must exist an index j\;(1 ≤ j ≤ N) such that S_{j} =  '1'  and \mid i - j \mid = K, where \mid x \mid denotes the absolute value of x.

For example, if K = 1, "00", "110", "011011" are 1-balanced strings, while "010" , "1001" are not; if K = 2, "10101", "0101000101" are 2-balanced strings, while "0110" , "1001", "010" are not. 

Chef is given a binary string S of length N and an integer K. He can perform the following operation on the string:

Select an index of the string, and flip the character at that index. This means if the character was "0", it becomes "1", and vice versa.

What is the minimum number of operations Chef will have to perform so that the string becomes *K-balanced*?

------ 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, 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 operation Chef needs to perform on the given string to make it K-balanced.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ 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 ------ 
4
2 1
01
3 1
111
4 2
1101
5 3
11110

----- Sample Output 1 ------ 
1
0
1
2

----- explanation 1 ------ 
Test case $1$: Chef applies one operation on the index $2$ and the string becomes "00" which is a 1-balanced string.

Test case $2$: The given string is already 1-balanced.

Test case $3$: Chef applies one operation on the index $3$ and the string becomes "1111" which is a 2-balanced string.

Test case $4$: Chef applies one operation on the index $2$ and another operation on the index $3$. Hence, the string becomes "10010" which is a 3-balanced string.

Difficulty: HARD
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = str(input())
	s = list(['0'] * k + list(s) + ['0'] * k)
	c = 0
	for j in range(k, k + n):
		if s[j] == '1' and s[j - k] == '0' and (s[j + k] == '0'):
			c += 1
			if j + k < k + n:
				s[j + k] = '1'
	print(c)


try:
	for t in range(int(input())):
		(N, K) = map(int, input().split())
		S = str(input())
		S = list(['0'] * K + list(S) + ['0'] * K)
		count = 0
		for i in range(K, K + N):
			if S[i] == '1' and S[i - K] == '0' and (S[i + K] == '0'):
				count += 1
				if i + K < K + N:
					S[i + K] = '1'
		print(count)
except:
	pass


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = list(input())
	count = 0
	for i in range(n):
		if s[i] == '0':
			continue
		if i + k < n and s[i + k] == '1' or (i - k >= 0 and s[i - k] == '1'):
			continue
		if i + k < n:
			s[i + k] = '1'
		else:
			s[i] = '0'
		count += 1
	print(count)


for test in range(int(input())):
	(n, k) = map(int, input().split())
	str = list(input())
	if str.count('0') == n:
		print(0)
	else:
		q = 0
		for i in range(n):
			if str[i] == '0':
				continue
			elif i + k < n and str[i + k] == '1' or (i - k >= 0 and str[i - k] == '1'):
				continue
			elif i + k < n:
				str[i + k] = '1'
				q += 1
			else:
				str[i] = '0'
				q += 1
		print(q)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ai = []
	for i in range(n):
		ai.append(int(s[i]))
	c = 0
	for i in range(n):
		if ai[i] == 1:
			if i + k >= n:
				if ai[i - k] == 0 or i - k < 0:
					ai[i] = 0
					c = c + 1
			elif i < k:
				if ai[i + k] == 0:
					ai[i + k] = 1
					c = c + 1
			elif ai[i + k] == 0 and ai[i - k] == 0:
				ai[i + k] = 1
				c = c + 1
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input().strip('\n'))
	ans = s.count('1')
	res = 0
	for i in range(n):
		if s[i] == '1':
			c = 0
			t = 0
			if i + k < n:
				c += 1
				if s[i + k] == '1':
					t += 1
			if i - k >= 0:
				c += 1
				if s[i - k] == '1':
					t += 1
			if c == 0:
				res += 1
				s[i] = '0'
			if c > 0:
				if t == 0:
					res += 1
					if i + k < n:
						s[i + k] = '1'
					else:
						s[i - k] = '1'
	print(min(res, ans))


def solveA():
	for _ in range(int(input())):
		print('YES' if input().count('1') > 3 else 'NO')

def solveB():
	for _ in range(int(input())):
		N = int(input())
		if N == 1:
			print('3')
		elif N == 2:
			print('21')
		else:
			print('11' + '0' * (N - 3) + '1')

def solveC():
	from itertools import permutations
	for _ in range(int(input())):
		T = [int(x) for x in input().split()]
		M = [int(x) for x in input().split()]
		ans = 0
		for i in range(21):
			for j in range(21):
				for k in range(21):
					if i * T[0] + j * T[1] + k * T[2] <= 240:
						temp = i * M[0] + j * M[1] + k * M[2]
						ans = max(ans, temp)
		print(ans)

def solveD():
	index = set()
	for _ in range(int(input())):
		(N, K) = [int(x) for x in input().split()]
		S = input() + '0' * K
		ans = 0
		index.clear()
		for i in range(K):
			if S[i] == '1' and S[i + K] == '0':
				ans += 1
				index.add(i + K)
		for i in range(K, N):
			if S[i] == '1' and S[i - K] == '0' and (S[i + K] == '0') and (i - K not in index):
				ans += 1
				index.add(i + K)
		print(ans)
solveD()


def solveA():
	for _ in range(int(input())):
		print('YES' if input().count('1') > 3 else 'NO')

def solveB():
	for _ in range(int(input())):
		N = int(input())
		if N == 1:
			print('3')
		elif N == 2:
			print('21')
		else:
			print('11' + '0' * (N - 3) + '1')

def solveC():
	from itertools import permutations
	for _ in range(int(input())):
		T = [int(x) for x in input().split()]
		M = [int(x) for x in input().split()]
		ans = 0
		for i in range(21):
			for j in range(21):
				for k in range(21):
					if i * T[0] + j * T[1] + k * T[2] <= 240:
						temp = i * M[0] + j * M[1] + k * M[2]
						ans = max(ans, temp)
		print(ans)

def solveD():
	for _ in range(int(input())):
		(N, K) = [int(x) for x in input().split()]
		S = [int(x) for x in input()]
		if K >= N:
			print(S.count(1))
			continue
		mod_k = list(S[:K])
		ans = 0
		for (i, s) in enumerate(S[K:]):
			ik = i % K
			if s:
				if mod_k[ik]:
					mod_k[ik] += 1
				else:
					mod_k[ik] = 1
			elif not mod_k[ik]:
				continue
			elif mod_k[ik] == 1:
				ans += 1
				mod_k[ik] += 1
			else:
				mod_k[ik] = 0
		ans += mod_k.count(1)
		print(ans)
solveD()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	c = 0
	for i in range(n):
		if s[i] == '1':
			if i >= k and s[i - k] == '1' or (i + k < n and s[i + k] == '1'):
				continue
			if i + k < n:
				s[i + k] = '1'
			c += 1
	print(c)


for q in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	s = list(s)
	ans = 0
	for i in range(n):
		if s[i] == '0':
			continue
		flag = False
		temp1 = abs(i + k)
		temp2 = i - k
		if temp1 < n:
			if s[i] == s[temp1]:
				flag = True
		if temp2 >= 0 and (not flag):
			if s[i] == s[temp2]:
				flag = True
		if temp1 > n - 1 and temp2 < 0:
			s[i] = '0'
			ans += 1
		if not flag:
			if temp1 < n:
				s[temp1] = '1'
				ans += 1
			elif temp2 >= 0:
				s[temp2] = '1'
				ans += 1
	print(ans)


def k_balanced(N, K, S):
	count = 0
	index = []
	S += K * '0'
	for i in range(K):
		if S[i] == '1':
			if S[i + K] == '0':
				count += 1
				index.append(i + K)
	for i in range(K, N):
		if S[i] == '1':
			if S[i + K] == '0' and S[i - K] == '0' and (i - K not in index):
				count += 1
				index.append(i + K)
	return count
t = int(input())
ans = []
for i in range(t):
	(N, K) = map(int, input().split())
	S = input()
	ans.append(k_balanced(N, K, S))
for i in range(t):
	print(ans[i])


I = input
t = int(I())
for _ in range(t):
	(n, k) = map(int, I().split())
	a = [*map(int, I())] + [0] * k
	a = [a[i] and (not (a[i - k] or a[i + k])) for i in range(n)]
	k *= 2
	for i in range(k, n):
		a[i] &= ~a[i - k]
	print(sum(a))


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().strip()
	ans = 0
	s = list(s)
	for i in range(n):
		flag = 0
		if s[i] == '1':
			if i + k >= n and i - k < 0:
				s[i] = '0'
				ans += 1
			else:
				if i + k < n and s[i + k] == '1':
					continue
				if i - k >= 0 and s[i - k] == '1':
					continue
				if i + k < n:
					s[i + k] = '1'
				else:
					s[i - k] = '1'
				ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(input())
	count = 0
	for i in range(n):
		if l[i] == '1':
			if i < k and i + k < n:
				if l[i + k] == '0':
					count += 1
					l[i + k] = '1'
			elif i >= k and i + k < n:
				if l[i + k] == '0' and l[i - k] == '0':
					count += 1
					l[i + k] = '1'
			elif i >= k and i + k > n - 1:
				if l[i - k] == '0':
					count += 1
					l[i] = '0'
			elif i < k and i + k > n - 1:
				count += 1
				l[i] = '0'
	print(count)


t = int(input())
for i in range(t):
	(n, k) = tuple(map(int, input().split()))
	s = input()
	ar = list(s)
	count = 0
	for i in range(len(s)):
		if ar[i] == '1' and i + k < n and (i - k >= 0):
			if ar[i + k] != '1' and ar[i - k] != '1':
				ar[i + k] = '1'
				count += 1
		elif ar[i] == '1' and i + k < n:
			if ar[i + k] != '1':
				ar[i + k] = '1'
				count += 1
		elif ar[i] == '1' and i - k >= 0:
			if ar[i - k] != '1':
				ar[i - k] = '1'
				count += 1
		elif ar[i] == '1':
			ar[i] = '0'
			count += 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	cnt = 0
	s = list(k * '0' + input() + k * '0')
	for i in range(k, k + n):
		if s[i] == '1':
			if s[i + k] != '1' and s[i - k] != '1':
				s[i + k] = '1'
				cnt += 1
	print(cnt)


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


def addit(s):
	le = len(s)
	c = 0
	for i in range(le):
		if s[i] == '1':
			if i - 1 >= 0 and s[i - 1] == '1':
				continue
			if i + 1 < le and s[i + 1] == '1':
				continue
			if i + 1 < le:
				s = s[:i + 1] + '1' + s[i + 2:]
			else:
				s = s[:i] + '0' + s[i + 1:]
			c += 1
	return c
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	li = [''] * k
	for i in range(n):
		li[i % k] += s[i]
	ans = 0
	for i in range(k):
		ans += addit(li[i])
	print(ans)


test = int(input())
for i in range(0, test):
	(n, k) = map(int, input().split())
	s = input()
	current = -1
	l = []
	leader = [0] * n
	counter = 0
	for i in s:
		l.append(int(i))
	for i in range(0, n):
		if n - 1 - i >= k:
			if l[i] == 1:
				if leader[i] == 0:
					if l[i + k] == 1:
						leader[i + k] = 1
						leader[i] = 1
						continue
					else:
						l[i + k] = 1
						leader[i] = 1
						leader[i + k] = 1
						counter = counter + 1
				else:
					leader[i + k] = 1
		elif l[i] == 1 and leader[i] == 0:
			counter = counter + 1
	print(counter)


from itertools import islice
I = input
t = int(I())
for _ in range(t):
	(n, k) = map(int, I().split())
	a = [*map(int, I())] + [0] * k
	a = [a[i] and (not (a[i - k] or a[i + k])) for i in range(n)]
	k *= 2
	r = sum(islice(a, k))
	for i in range(k, n):
		if a[i]:
			if a[i - k]:
				a[i] = 0
			else:
				r += 1
	print(r)


I = input
t = int(I())
for _ in range(t):
	(n, k) = map(int, I().split())
	a = [*map(int, I())] + [0] * k
	a = [a[i] and (not (a[i - k] or a[i + k])) for i in range(n)]
	r = 0
	k *= 2
	a = [0] * k + a
	for i in range(k, n + k):
		if a[i]:
			if a[i - k]:
				a[i] = 0
			else:
				r += 1
	print(r)


for t in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	s = []
	for i in S:
		s.append(int(i))
	ope = 0
	for i in range(len(s)):
		if s[i] == 0:
			continue
		if i + K < N and s[i + K] == 1 or (i - K >= 0 and s[i - K] == 1):
			continue
		if i + K < N and s[i + K] == 0:
			s[i + K] = 1
			ope += 1
		else:
			s[i] = 0
			ope += 1
	print(ope)


t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	arr = list(str(input()))
	count = 0
	for i in range(n):
		if arr[i] == '0':
			continue
		if i + k < n:
			if arr[i + k] == '1':
				continue
		if i - k >= 0:
			if arr[i - k] == '1':
				continue
		if i + k < n:
			arr[i + k] = '1'
		else:
			arr[i] = '0'
		count += 1
	print(count)


try:
	for i in range(int(input())):
		(n, k) = map(int, input().split())
		ar = list(input())
		count = 0
		for i in range(n):
			if ar[i] == '1' and i + k < n and (i - k >= 0):
				if ar[i + k] != '1' and ar[i - k] != '1':
					ar[i + k] = '1'
					count += 1
			elif ar[i] == '1' and i + k < n:
				if ar[i + k] != '1':
					ar[i + k] = '1'
					count += 1
			elif ar[i] == '1' and i - k >= 0:
				if ar[i - k] != '1':
					ar[i - k] = '1'
					count += 1
			elif ar[i] == '1':
				ar[i] = '0'
				count += 1
		print(count)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = []
	for i in range(n):
		if s[i] == '1':
			if i - k >= 0 and s[i - k] == '1':
				pass
			elif i + k < n and s[k + i] == '1':
				pass
			else:
				l.append(i)
	m = len(l)
	s = set(l)
	c = 0
	for i in range(m):
		if l[i] in s:
			if l[i] + 2 * k in s:
				s.remove(l[i] + 2 * k)
			c += 1
	print(c)


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


try:
	t = int(input())
	for i in range(t):
		(n, k) = [int(j) for j in input().split(' ')]
		arr = input()
		count = 0
		a = []
		for j in range(n):
			a.append(arr[j])
		for j in range(n):
			if a[j] == '1':
				if j - k >= 0 and a[j - k] == '1':
					continue
				if j + k < n and a[j + k] == '1':
					continue
				if j + k < n:
					a[j + k] = '1'
				else:
					a[j] = '0'
				count += 1
		print(count)
except:
	pass


t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	for i in range(n):
		if s[i] == '1':
			st = 0
			if i - k >= 0:
				if s[i - k] == '1':
					st = -1
			if st == 0:
				if i + k < n:
					if s[i + k] == '1':
						st = 1
					else:
						try:
							s = s[:i + k] + '1' + s[i + k + 1:]
						except:
							s = s[:i + k] + '1'
						ans += 1
				else:
					ans += 1
					try:
						s = s[:i] + '0' + s[i + 1:]
					except:
						s = s[:i] + '0'
	print(ans)


import sys
input = sys.stdin.readline

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

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, chain, combinations, groupby
from operator import itemgetter
from types import GeneratorType
from typing import Iterable, TypeVar, Union
for _ in range(II()):
	(n, k) = LI()
	s = [int(x) for x in I()]
	f = [0] * n
	for i in range(n):
		if s[i] == 1:
			if i - k >= 0 and s[i - k] == 1 or (i + k < n and s[i + k] == 1):
				continue
			f[i] = 1
	ans = 0
	for i in range(n):
		if f[i] == 1:
			if i + 2 * k < n and f[i + 2 * k] == 1:
				f[i + 2 * k] = 0
			ans += 1
	print(ans)


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


t = int(input())
while t:
	(n, k) = map(int, input().split())
	s = input()
	l = []
	m = [0 for i in range(0, 2 * n + 1)]
	result = 0
	for i in range(n):
		if s[i] == '1':
			l.append(i)
			m[i] += 1
	for i in range(len(l)):
		if m[l[i] - k] and l[i] - k >= 0:
			continue
		if m[l[i] + k]:
			continue
		result += 1
		m[l[i] + k] += 1
	print(result)
	t -= 1


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	count = 0
	index = []
	S += K * '0'
	for i in range(K):
		if S[i] == '1':
			if S[i + K] == '0':
				count += 1
				index.append(i + K)
	for i in range(K, N):
		if S[i] == '1':
			if S[i + K] == '0' and S[i - K] == '0' and (i - K not in index):
				count += 1
				index.append(i + K)
	print(count)


for k in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	p = []
	for i in S:
		p.append(int(i))
	l = 0
	for i in range(N):
		if p[i] == 1 and i + K < N and (i - K >= 0):
			if p[i + K] != 1 and p[i - K] != 1:
				p[i + K] = 1
				l += 1
		elif p[i] == 1 and i + K < N:
			if p[i + K] != 1:
				p[i + K] = 1
				l += 1
		elif p[i] == 1 and i - K >= 0:
			if p[i - K] != 1:
				p[i - K] = 1
				l += 1
		elif p[i] == 1:
			p[i] = 0
			l += 1
	print(l)


def solve(s, n, k):
	visited = [False for i in range(n)]
	ans = 0
	for i in range(n):
		if not visited[i]:
			visited[i] = True
			if s[i] == '1':
				if i + k < n:
					visited[i + k] = True
					if s[i + k] == '0':
						ans += 1
				else:
					ans += 1
		elif i + k < n and s[i + k] == '1':
			visited[i + k] = True
	return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(solve(s, n, k))


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


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	lis = list(input())
	count = 0
	for i in range(n):
		if lis[i] == '0':
			continue
		if i + k < n and lis[i + k] == '1' or (i - k >= 0 and lis[i - k] == '1'):
			continue
		if i + k < n:
			lis[i + k] = '1'
		else:
			lis[i] = '0'
		count += 1
	print(count)


from collections import defaultdict
for _ in range(int(input())):

	def solve(t):
		ans = 0
		for i in range(len(t)):
			if t[i] == '1':
				if i - 1 >= 0 and t[i - 1] == '1':
					continue
				if i + 1 < len(t) and t[i + 1] == '1':
					continue
				if i + 1 < n:
					t = t[:i + 1] + '1' + t[i + 2:]
				else:
					t = t[:i - 1] + '1' + t[i:]
				ans += 1
		return ans
	(n, k) = map(int, input().split())
	s = input()
	val = {}
	for i in range(len(s)):
		g = i % k
		if not g in val:
			val[g] = ''
		val[g] += s[i]
	res = 0
	for l in val.values():
		res += solve(l)
	print(res)


def solve(n, k, s):
	count = 0
	for (index, value) in enumerate(s):
		if value == '0':
			continue
		if value == '1' and (index + k < n and s[index + k] == '1' or (index - k >= 0 and s[index - k] == '1')):
			continue
		elif index + k < n:
			s[index + k] = '1'
		else:
			s[index] = '0'
		count += 1
	return count
T = int(input())
while T:
	(n, k) = tuple(map(int, input().split()))
	lis = list(input())
	output = solve(n, k, lis)
	print(output)
	T -= 1


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


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


t = int(input())
while t > 0:
	(n, k) = [int(x) for x in input().split()]
	s = input()
	ans = 0
	s = list(s)
	for i in range(n):
		if s[i] == '1':
			if i + k < n and s[i + k] == '1' or (i - k >= 0 and s[i - k] == '1'):
				continue
			else:
				ans += 1
				if i + 2 * k < n and s[i + 2 * k] == '1':
					s[i + k] = '1'
	print(ans)
	t -= 1


def func():
	(N, K) = map(int, input().split())
	S = list(input())
	req = 0
	for i in range(N):
		if S[i] == '1':
			if i >= K and S[i - K] == '1' or (i <= N - K - 1 and S[i + K] == '1'):
				continue
			req += 1
			if i <= N - K - 1:
				S[i + K] = '1'
	print(req)
t = int(input())
for i in range(t):
	func()


for j in range(int(input())):
	(a, k) = map(int, input().split())
	c = input()
	b = []
	for i in c:
		b.append(i)
	ans = 0
	for i in range(len(b)):
		if b[i] == '1':
			if i - k >= 0 and b[i - k] == '1':
				continue
			if i + k <= a - 1 and b[i + k] == '1':
				continue
			if i + 2 * k <= a - 1 and b[i + 2 * k] == '1':
				b[i + k] = '1'
				ans += 1
				continue
			ans += 1
	print(ans)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

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

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, k) = mp()
	s = st()
	ans = 0
	for i in range(n):
		if s[i] == '1':
			if i - k >= 0 and i + k < n:
				if s[i - k] == '1' or s[i + k] == '1':
					continue
				else:
					s[i + k] = '1'
					ans += 1
			elif i + k < n:
				if s[i + k] == '1':
					continue
				else:
					s[i + k] = '1'
					ans += 1
			elif i - k >= 0:
				if s[i - k] != '1':
					s[i - k] = '1'
					ans += 1
			else:
				s[i] = '0'
				ans += 1
	print(ans)
for _ in range(inp()):
	solve()


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(nmbr()):
	ans = 0
	(n, k) = lst()
	s = list(input())
	for i in range(n):
		ch = s[i]
		if ch == '1':
			if i - k < 0 and i + k >= n:
				ans += 1
			elif i + k >= n and (i - k >= 0 and s[i - k] == '0'):
				ans += 1
			elif i - k >= 0 and s[i - k] == '1':
				continue
			elif i + k < n and s[i + k] == '0':
				s[i + k] = '1'
				ans += 1
	print(ans)


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	S = list(input())
	ans = 0
	for i in range(N):
		if S[i] == '1':
			if i >= K and S[i - K] == '1' or (i <= N - K - 1 and S[i + K] == '1'):
				continue
			ans += 1
			if i <= N - K - 1:
				S[i + K] = '1'
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	str = input()
	list1 = list(str)
	list2 = list(str)
	count = 0
	count1 = 0
	for i in range(0, len(list1)):
		if list1[i] == '1':
			if i - k >= 0 and i + k < n:
				if list1[i - k] == '1' or list1[i + k] == '1':
					continue
				else:
					list1[i + k] = '1'
					count += 1
			elif i - k >= 0 and i + k >= n:
				if list1[i - k] == '1':
					continue
				else:
					list1[i - k] = '1'
					count += 1
			elif i - k < 0 and i + k < n:
				if list1[i + k] == '1':
					continue
				else:
					list1[i + k] = '1'
					count += 1
			else:
				list1[i] = '0'
				count += 1
	for i in range(len(list2) - 1, -1, -1):
		if list2[i] == '1':
			if i - k >= 0 and i + k < n:
				if list2[i - k] == '1' or list2[i + k] == '1':
					continue
				else:
					list2[i - k] = '1'
					count1 += 1
			elif i - k >= 0 and i + k >= n:
				if list2[i - k] == '1':
					continue
				else:
					list2[i - k] = '1'
					count1 += 1
			elif i - k < 0 and i + k < n:
				if list2[i + k] == '1':
					continue
				else:
					list2[i + k] = '1'
					count1 += 1
			else:
				list2[i] = '0'
				count1 += 1
	print(min(count, count1))


for t in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	count = 0
	li = []
	for i in range(n):
		if s[i] == '1':
			if i - k >= 0:
				if s[i - k] == '1' or i - k in li:
					continue
			if i + k < n:
				if s[i + k] == '1' or i + k in li:
					continue
			count += 1
			if i + k < n:
				li.append(i + k)
			else:
				li.append(i - k)
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, list(input())))
	p = 0
	for i in range(n):
		if l[i] == 1:
			x = 0
			y = 0
			z = 0
			if i + k < n:
				if l[i + k] == 1:
					continue
				else:
					x = 1
			else:
				x = 1
			if i - k >= 0:
				if l[i - k] == 1:
					continue
				else:
					y = 1
			else:
				y = 1
			if x == 1 and y == 1:
				if i + k < n:
					l[i + k] = 1
				elif i - k >= 0:
					l[i - k] = 1
				else:
					l[i] = 0
				p = p + 1
	print(p)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(str(input()))
	(a, b) = (0, 0)
	for i in range(n):
		t = 0
		if s[i] == '1':
			if i + k >= n and i - k < 0:
				s[i] = '0'
				a += 1
				continue
			if i + k < n and i - k >= 0:
				if s[i + k] == '0' and s[i - k] == '0':
					a += 1
					s[i + k] = '1'
					continue
			elif i + k < n:
				if s[i + k] == '0':
					a += 1
					s[i + k] = '1'
			elif s[i - k] == '0':
				a += 1
				s[i - k] = '1'
	print(a)


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()
	re = 0
	for i in range(k):
		test = ''
		for j in range(i, n, k):
			test += s[j]
		co = 0
		ind = []
		for j in range(len(test)):
			if test[j] == '1':
				co += 1
				continue
			else:
				if co == 1:
					ind.append(j - 1)
				co = 0
		if co == 1:
			ind.append(len(test) - 1)
		if len(ind):
			if len(ind) == 1:
				re += 1
			else:
				j = 0
				while j < len(ind) - 1:
					if ind[j + 1] - ind[j] > 2:
						re += 1
						j += 1
					else:
						re += 1
						j += 2
				if j == len(ind) - 1:
					re += 1
	print(min(re, s.count('1')))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	v = []
	cnt = [0] * (2 * n)
	for i in range(n):
		if s[i] == '1':
			v.append(i)
			cnt[i] += 1
	ans = 0
	for i in range(len(v)):
		if v[i] - k >= 0 and cnt[v[i] - k]:
			continue
		if cnt[v[i] + k]:
			continue
		ans += 1
		cnt[v[i] + k] += 1
	print(ans)


from os import times
import sys
from collections import deque
import heapq
import bisect
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
test_case = 1
test_case = int(input())
sys.setrecursionlimit(10 ** 6)

def ans():
	(n, k) = ari()
	cost = 0
	st = cis()
	st = list('0' * k + st + '0' * k)
	for i in range(k, k + n):
		if st[i] == '1':
			if st[i + k] != '1' and st[i - k] != '1':
				st[i + k] = '1'
				cost += 1
	print(cost)
for _ in range(test_case):
	ans()


def mgc(x, k, n):
	ans = 0
	bst = set()
	for i in range(n):
		if x[i] == '1':
			if i in bst:
				if i + k < n:
					if x[i + k] == '1':
						bst.add(i + k)
				continue
			if i + k >= n:
				ans += 1
				continue
			if x[i + k] != '1':
				ans += 1
			s[i + k] = '1'
			bst.add(i + k)
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	print(mgc(s, k, n))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	a = [s[i] for i in range(n)]
	ans = 0
	for i in range(n):
		if a[i] == '1':
			if i - k >= 0 and a[i - k] == '1':
				continue
			if i + k < n and a[i + k] == '1':
				continue
			if i + 2 * k < n and a[i + 2 * k] == '1':
				a[i + k] = '1'
			ans += 1
	print(ans)


from math import ceil, log, floor
from collections import defaultdict
import sys
import os.path
sys.setrecursionlimit(200000)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r+')
	sys.stdout = open('output.txt', 'w')

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


def cal(n, k, a):
	convert = 0
	a = list(a)
	for i in range(n):
		if a[i] == '1':
			if i + k < n and i - k >= 0:
				if a[i + k] == '1':
					a[i] = '2'
					a[i + k] = '2'
				elif a[i - k] == '2':
					a[i] = '2'
				elif a[i + k] == '0':
					convert += 1
					a[i] = '2'
					a[i + k] = '2'
			elif i + k < n:
				if a[i + k] == '1':
					a[i] = '2'
					a[i + k] = '2'
				else:
					convert += 1
					a[i] = '2'
					a[i + k] = '2'
			elif i - k >= 0:
				if a[i - k] == '2':
					a[i] = '2'
				elif a[i - k] == '0':
					a[i] = '2'
					convert += 1
			else:
				convert += 1
				a[i] = '0'
	return convert
t = int(input())
for i in range(t):
	m = list(map(int, input().split()))
	l = input()
	print(cal(m[0], m[1], l))


for j in range(int(input())):
	(N, K) = [int(i) for i in input().split()]
	result = 0
	string = [int(i) for i in input()]
	for i in range(len(string)):
		if string[i] == 1:
			if i < K:
				if i + K < len(string):
					if string[i + K] == 0:
						result += 1
						string[i + K] = 1
				else:
					result += 1
					string[i] = 0
			elif i > N - K - 1:
				if i - K >= 0:
					if string[i - K] == 0:
						result += 1
						string[i - K] = 1
				else:
					result += 1
					string[i] = 0
			elif string[i + K] == 0 and string[i - K] == 0:
				result += 1
				string[i + K] = 1
	print(result)


T = int(input())
out = []
for _ in range(T):
	(n, k) = list(map(int, input().split(' ')))
	string = input()
	swaps = 0
	done = set()
	for i in range(n):
		if i in done:
			done.remove(i)
			if i + k < n and string[i + k] == '1':
				done.add(i + k)
			continue
		if string[i] == '1':
			if i + k >= n:
				swaps += 1
				continue
			if string[i + k] == '1':
				done.add(i + k)
			elif i + k * 2 < n and string[i + k * 2] == '1':
				done.add(i + k)
				swaps += 1
			else:
				swaps += 1
	print(swaps)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = str(input())
	res = []
	for i in range(n):
		if l[i] == '1':
			if i >= k and l[i - k] == '1' or (i + k < n and l[i + k]) == '1':
				continue
			else:
				res.append(i)
	ans = set()
	x = 0
	for i in res:
		if i + k not in ans and i - k not in ans:
			if i + k < n:
				ans.add(i + k)
			else:
				ans.add(i - k)
			x += 1
	print(x)


from copy import deepcopy
cases = int(input())
for _ in range(cases):
	(n, k) = map(int, input().split())
	s = input()
	ones = [i for (i, char) in enumerate(s) if char == '1']
	st = set(ones)
	ans = 0
	for n in ones:
		if n + k in st or n - k in st:
			continue
		ans += 1
		st.add(n + k)
	print(ans)


from sys import stdin
input = stdin.readline

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