You are given a binary string S of length N and an integer K. You can perform the following operation on the string:
Select a *prefix* of the string S and flip all the characters of the prefix. A flip corresponds to changing 0 to 1 and vice-versa.

Find the minimum number of operations required to obtain a substring of length K such that all characters of the substring are 1.

Note:
A prefix is obtained by deleting some (possibly zero) characters from the end of the string.
A substring is obtained by deleting some (possibly zero) characters from the beginning of the string and some (possibly zero) characters from the end of the string.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and K — the length of the string and the length length of substring containing all 1s we want to achieve.
- The next line contains the binary string S.

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

For each test case, output on a new line, the minimum number of operations required to obtain a substring of length K such that all characters of the substring are 1.

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

$1 ≤ T ≤ 2000$
$1 ≤ K ≤N ≤ 3\cdot 10^{5}$
$S$ consists of $0$ and $1$ only.
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3 3
000
4 2
0110
5 3
10101

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

----- explanation 1 ------ 
Test case $1$: We need to obtain a substring containing three $1$s. Using one operation, we can select the prefix $S[1,3]$ and flip all the characters in the prefix. Thus, the string becomes $111$.  

Test case $2$: The string already contains a substring having two $1$s. Thus, we do not need any operation.

Test case $3$: We need to obtain a substring containing three $1$s. We can do so using $2$ operations:
- Operation $1$: Select the prefix $S[1, 4]$ and flip all characters in the prefix. Thus, the string becomes $01011$.
- Operation $2$: Select the prefix $S[1, 3]$ and flip all characters in the prefix. Thus, the string becomes $10111$.

Thus, we have a substring $S[3,5]$ of length $3$ where all characters of the substring are $1$. It can be shown that we cannot obtain such substring using less than $2$ operations.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures


Solutions:
from math import inf
from collections import defaultdict
from collections import OrderedDict
from collections import Counter
from collections import ChainMap

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

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

def main():
	for _ in range(int(input())):
		(n, k) = getinp()
		s = input()
		if k == 1:
			print(0) if '1' in s else print(1)
		else:
			different = 0
			prev = ''
			pre = [0] * (n + 1)
			for i in range(n):
				if prev:
					if prev != s[i]:
						different += 1
						prev = s[i]
				else:
					prev = s[i]
				pre[i] = different
			if n == k:
				diff = pre[k - 1] - pre[0]
				if s[k - 1] == '0':
					diff += 1
				print(diff)
			else:
				minn = pre[k - 1] - pre[0]
				if s[k - 1] == '0':
					minn += 1
				for i in range(1, n):
					if k + i - 1 < n:
						temp = pre[k + i - 1] - pre[i]
						if s[k + i - 1] == '0':
							temp += 1
					minn = min(temp, minn)
				print(minn)
main()


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(input())
	x = list()
	y = list()
	for i in range(0, a):
		if i == 0:
			x.append(0)
		elif l[i - 1] == l[i]:
			x.append(x[i - 1])
		else:
			x.append(x[i - 1] + 1)
		if i >= b - 1:
			if l[i] == '1':
				y.append(x[i] - x[i - b + 1])
			else:
				y.append(x[i] - x[i - b + 1] + 1)
	print(min(y))


def T(S):
	N = len(S)
	x = 0
	for j in range(N - 1):
		if S[j] == '0' and S[j + 1] == '1':
			x += 1
		if S[j] == '1' and S[j + 1] == '0':
			x += 1
	return x
a = int(input())
for i in range(a):
	(N, K) = map(int, input().split())
	S = input()
	x = T(S[:K])
	y = 0
	if x == 0:
		if S[0] == '0':
			y = 1
		else:
			y = 0
	elif S[K - 1] == '1':
		y = x
	else:
		y = x + 1
	A = [y]
	p = S[0]
	q = S[K - 1]
	for j in range(K, N):
		if S[j] != q:
			x += 1
		if S[j - K + 1] != p:
			x -= 1
		q = S[j]
		p = S[j - K + 1]
		if q == '1':
			A.append(x)
		else:
			A.append(x + 1)
	ans = min(A)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

def readInt():
	return int(input())

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

def readStringList():
	return list(input())

def readStringListWithSpace():
	return list(input().split())

def readString():
	return input()

def execute():
	for _ in range(readInt()):
		(n, k) = readIntList()
		arr = readStringList()
		(l, r, res, count) = (0, k - 1, n, 1)
		for i in range(r):
			if arr[i] != arr[i + 1]:
				count += 1
		res = min(res, count - 1 if arr[r] == '1' else count)
		while r + 1 < n:
			l += 1
			if arr[l] != arr[l - 1]:
				count -= 1
			r += 1
			if arr[r] != arr[r - 1]:
				count += 1
			res = min(res, count - 1 if arr[r] == '1' else count)
		print(res)
execute()


T = int(input())
for i in range(0, T):
	(n, k) = map(int, input().split())
	s = input()
	segment = 1
	l = 0
	r = k - 1
	ans = n
	for i in range(0, r):
		if s[i] != s[i + 1]:
			segment += 1
	if s[r] == '0':
		ans = min(ans, segment)
	else:
		ans = min(ans, segment - 1)
	while r + 1 < n:
		l += 1
		if s[l] != s[l - 1]:
			segment -= 1
		r += 1
		if s[r] != s[r - 1]:
			segment += 1
		if s[r] == '0':
			ans = min(ans, segment)
		else:
			ans = min(ans, segment - 1)
	print(ans)


T = int(input())
for _ in range(T):
	(N, k) = map(int, input().split())
	S = input()
	(l, r) = (0, k - 1)
	ans = N
	seg = 1
	for i in range(1, k):
		if S[i - 1] != S[i]:
			seg += 1
	if S[r] == '1':
		ans = min(ans, seg - 1)
	else:
		ans = min(ans, seg)
	while r + 1 < N:
		(l, r) = (l + 1, r + 1)
		if S[l - 1] != S[l]:
			seg -= 1
		if S[r - 1] != S[r]:
			seg += 1
		if S[r] == '1':
			ans = min(ans, seg - 1)
		else:
			ans = min(ans, seg)
	print(ans)


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


import sys
import math
from math import inf

def main():
	(t, y, z, i, n, ct, x, p, j, max1, o, ans, z1, k) = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
	t = int(input())
	while t > 0:
		t -= 1
		(n, k) = map(int, input().split())
		s = input()
		(i, j, x) = (0, 0, 0)
		if k == 1:
			ans = 1
			for i in range(n):
				if s[i] == '1':
					ans = 0
			print(ans)
			continue
		ans = inf
		while j < n:
			if j - i + 1 < k:
				if j > 0 and s[j] != s[j - 1]:
					x += 1
			elif j - i + 1 == k:
				if j > 0 and s[j] != s[j - 1]:
					x += 1
				if x == 0 and s[j] == '0' and (s[i] == '0'):
					ans = min(ans, 1)
				elif s[j] == '0':
					ans = min(ans, x + 1)
				else:
					ans = min(ans, x)
				if i < n - 1 and s[i] != s[i + 1]:
					x -= 1
				i += 1
			j += 1
		print(ans)
main()


t = int(input())
for _ in range(t):
	(N, K) = [int(x) for x in input().split(' ')]
	s = ''.join([x for x in input().split(' ')])
	ls = list(s)
	pref = [0 for _ in range(len(ls))]
	for i in range(1, len(ls)):
		pref[i] = pref[i - 1]
		if ls[i] != ls[i - 1]:
			pref[i] += 1
	mn = 9999999999999999999
	for i in range(N - K + 1):
		if s[i + K - 1] == '1':
			mn = min(mn, pref[i + K - 1] - pref[i])
		else:
			mn = min(mn, pref[i + K - 1] - pref[i] + 1)
	print(mn)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	arr = [0] * (n + 1)
	for i in range(n):
		if i == 0:
			arr[i + 1] = 1
		elif s[i] != s[i - 1]:
			arr[i + 1] = arr[i] + 1
		else:
			arr[i + 1] = arr[i]
	m = k
	for j in range(n - k + 1):
		ss = j + 1
		e = j + k
		if s[j + k - 1] == '0':
			if ss == 0:
				c = arr[e]
				m = min(m, c)
			elif arr[e] == arr[ss - 1]:
				c = 1
				m = min(m, c)
			elif arr[ss] == arr[ss - 1]:
				c = arr[e] - arr[ss - 1] + 1
				m = min(m, c)
				pass
			else:
				c = arr[e] - arr[ss - 1]
				m = min(m, c)
		elif ss == 0:
			c = arr[e] - 1
			m = min(m, c)
		elif arr[e] == arr[ss - 1]:
			c = 0
			m = min(m, c)
		elif arr[ss] == arr[ss - 1]:
			c = arr[e] - arr[ss - 1] - 1 + 1
			m = min(m, c)
		else:
			c = arr[e] - arr[ss - 1] - 1
			m = min(m, c)
	print(m)


def getList(val=1):
	if not val:
		return list(map(str, input().split()))
	return list(map(int, input().split()))

def getTuple(val=1):
	if not val:
		return map(str, input().split())
	return map(int, input().split())
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = input()
	if k == 1:
		if '1' in arr:
			print(0)
		else:
			print(1)
		continue
	seg = 0
	prev = ''
	for i in range(k):
		if arr[i] != prev:
			seg += 1
		prev = arr[i]
	ans = seg
	if prev == '1':
		ans = min(ans, seg - 1)
	for i in range(1, len(arr)):
		j = i + k - 1
		if j >= len(arr):
			break
		if arr[j] != arr[j - 1]:
			seg += 1
		if arr[i] != arr[i - 1]:
			seg -= 1
		if arr[j] == '1':
			ans = min(ans, seg - 1)
		ans = min(ans, seg)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if k == 1:
		print(0) if '1' in s else print(1)
	else:
		different = 0
		prev = ''
		pre = [0] * (n + 1)
		for i in range(n):
			if prev:
				if prev != s[i]:
					different += 1
					prev = s[i]
			else:
				prev = s[i]
			pre[i] = different
		if n == k:
			diff = pre[k - 1] - pre[0]
			if s[k - 1] == '0':
				diff += 1
			print(diff)
		else:
			minn = pre[k - 1] - pre[0]
			if s[k - 1] == '0':
				minn += 1
			for i in range(1, n):
				if k + i - 1 < n:
					temp = pre[k + i - 1] - pre[i]
					if s[k + i - 1] == '0':
						temp += 1
				minn = min(temp, minn)
			print(minn)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l1 = []
	cnt = 0
	if k * '1' in s:
		print(0)
	elif k * '0' in s:
		print(1)
	else:
		for c in range(0, k):
			if c == 0:
				continue
			elif s[c] == s[c - 1]:
				continue
			else:
				cnt += 1
		if s[k - 1] == '0':
			l1.append(cnt + 1)
		else:
			l1.append(cnt)
		for h in range(1, n - k + 1):
			j = h + k - 1
			if s[h - 1] != s[h] and s[j - 1] == s[j]:
				cnt -= 1
			if s[h - 1] == s[h] and s[j - 1] != s[j]:
				cnt += 1
			if s[j] == '0':
				l1.append(cnt + 1)
			else:
				l1.append(cnt)
		print(min(l1))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	s1 = '0' * k
	s2 = '1' * k
	if s2 in s:
		print('0')
	elif s1 in s:
		print('1')
	else:
		cnt = 0
		l1 = []
		for c in range(0, k):
			if c == 0:
				continue
			elif s[c] == s[c - 1]:
				continue
			else:
				cnt += 1
		if s[k - 1] == '0':
			l1.append(cnt + 1)
		else:
			l1.append(cnt)
		for h in range(1, n - k + 1):
			j = h + k - 1
			if s[h - 1] != s[h] and s[j - 1] == s[j]:
				cnt -= 1
			if s[h - 1] == s[h] and s[j - 1] != s[j]:
				cnt += 1
			if s[j] == '0':
				l1.append(cnt + 1)
			else:
				l1.append(cnt)
		print(min(l1))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	b = input()
	t = []
	c = 0
	for i in range(k - 1):
		if b[i] != b[i + 1] and b[i] == '1' and (b[i + 1] == '0'):
			c += 2
	if b[0] == '0':
		c += 1
	t.append(c)
	l = b[0]
	r = b[k - 1]
	for i in range(n - k):
		if b[i + 1] != b[i]:
			c -= 1
		if b[k + i] != b[k + i - 1] and b[k + i - 1] == '1' and (b[i + k] == '0'):
			c += 2
		t.append(c)
	print(min(t))


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

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

def main():
	for _ in range(int(input())):
		(n, k) = getinp()
		s = input()
		if k == 1:
			print(0) if '1' in s else print(1)
		else:
			different = 0
			prev = ''
			pre = [0] * (n + 1)
			for i in range(n):
				if prev:
					if prev != s[i]:
						different += 1
						prev = s[i]
				else:
					prev = s[i]
				pre[i] = different
			if n == k:
				diff = pre[k - 1] - pre[0]
				if s[k - 1] == '0':
					diff += 1
				print(diff)
			else:
				minn = pre[k - 1] - pre[0]
				if s[k - 1] == '0':
					minn += 1
				for i in range(1, n):
					if k + i - 1 < n:
						temp = pre[k + i - 1] - pre[i]
						if s[k + i - 1] == '0':
							temp += 1
					minn = min(temp, minn)
				print(minn)
main()


def findOps(n, s):
	cnt = 0
	ops = [0] * n
	for i in range(1, n):
		ops[i] = ops[i - 1] + int(s[i - 1] != s[i])
	return ops

def solve(n, k, s):
	ops = findOps(n, s)
	res = float('inf')
	l = 0
	for r in range(k - 1, n):
		res = min(res, ops[r] - ops[l] + int(s[r] != '1'))
		l += 1
	return res
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split(' ')))
	s = input()
	print(solve(n, k, s))


def preFlip(n, k, s):
	ans = n
	blocks = 1
	for i in range(1, k):
		blocks += s[i] != s[i - 1]
	if s[k - 1] == '1':
		ans = blocks - 1
	else:
		ans = blocks
	for i in range(k, n):
		blocks += s[i] != s[i - 1]
		blocks -= s[i - k] != s[i - k + 1]
		if s[i] == '1':
			ans = min(ans, blocks - 1)
		else:
			ans = min(ans, blocks)
	return ans
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	print(preFlip(n, k, s))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	cnt = 0
	l = []
	if k * '1' in s:
		print(0)
	elif k * '0' in s:
		print(1)
	else:
		for h in range(0, k):
			if h == 0:
				continue
			elif s[h] == s[h - 1]:
				continue
			else:
				cnt += 1
		if s[k - 1] == '0':
			l.append(cnt + 1)
		else:
			l.append(cnt)
		for i in range(1, n - k + 1):
			j = i + k - 1
			if s[i - 1] != s[i] and s[j - 1] == s[j]:
				cnt -= 1
			if s[i - 1] == s[i] and s[j - 1] != s[j]:
				cnt += 1
			if s[j] == '0':
				l.append(cnt + 1)
			else:
				l.append(cnt)
		print(min(l))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if '1' * k in s:
		print(0)
	elif '0' * k in s:
		print(1)
	else:
		bit = 0
		op = 0
		ans = n
		operations = [0] * n
		for i in range(1, n):
			operations[i] = operations[i - 1] + int(s[i] != s[i - 1])
			if i >= k - 1:
				ans = min(ans, operations[i] - operations[i - k + 1] + int(s[i] == '0'))
		print(ans)


a = int(input())
for i in range(a):
	(n, p) = map(int, input().split())
	b = input()
	co = 0
	j = []
	g = 0
	for i in range(n):
		if b[i] == '0':
			if g == 1:
				j.append([co, 1])
				co = 0
			co += 1
			g = 0
		if b[i] == '1':
			if g == 1:
				j.append([co, 0])
				co = 0
			co += 1
			g = 0
		if i != len(b) - 1:
			if b[i] == '0' and b[i + 1] == '1':
				g = 1
			if b[i] == '1' and b[i + 1] == '0':
				g = 1
	if b[-1] == '0':
		j.append([co, 0])
	else:
		j.append([co, 1])
	co = 0
	size = 10 ** 6
	l = 0
	r = 0
	si = 0
	su = 0
	while r < len(j):
		if su < p:
			su += j[r][0]
			si += 1
			r += 1
		if su >= p:
			if size > si and j[r - 1][1] == 1:
				size = si - 1
			elif size > si:
				size = si
			while su >= p:
				su -= j[l][0]
				l += 1
				si -= 1
			if size > si and j[r - 1][1] == 1:
				size = si
			elif size > si + 1 and j[r - 1][1] == 0:
				size = si + 1
		if size == 0:
			break
	print(size)


import os.path
from math import *
from collections import *
from random import *
from statistics import *
from re import *
import time
import sys
from itertools import *
mod = 1000000007
Min = float('-inf')
Max = float('inf')

def prmp(li):
	return sys.stdout.write(' '.join(map(str, li)) + '\n')

def nl(n):
	return sys.stdout.write(list(map(int, str(n))))

def sl(st):
	return sys.stdout.write(list(st.split()))

def prli(li):
	return sys.stdout.write(*li)

def prsli(li):
	return sys.stdout.write(*sorted(li))

def binToDec(st):
	return sys.stdout.write(int(st, 2))

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

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

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 ip():
	return int(sys.stdin.readline())

def gt_bit(val, bit_idx):
	return val & 1 << bit_idx

def st_bit(val, bit_idx):
	return val | 1 << bit_idx

def unst_bit(val, bit_idx):
	return val & ~(1 << bit_idx)

def tggl_bit(val, bit_idx):
	return val ^ 1 << bit_idx

def comp(n):
	return ~num

def slsb_(n):
	n &= n - 1
	return n

def lsb_(n):
	n &= -n
	print(n)

def div1(n):
	return n >> 1

def mul2(n):
	return num << 1

def sieve_(n):
	li = []
	for i in range(2, n + 1):
		if i not in li:
			print(i)
			for j in range(i * i, n + 1, i):
				li.append(j)
	return li

def lcm_(x, y):
	if x > y:
		maxi = x
	else:
		maxi = y
	while True:
		if maxi % x == 0 and maxi % y == 0:
			lcm = maxi
			break
		maxi += 1
	return lcm

def binomial(n, k):
	return 1 if k == 0 else 0 if n == 0 else Binomial(n - 1, k) + Binomial(n - 1, k - 1)

def binS(arr, x):
	l = 0
	r = len(arr) - 1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == x:
			return mid
		elif x < arr[mid]:
			r = mid - 1
		elif x > arr[mid]:
			l = mid + 1
	return -1
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	ans = float('inf')
	(a, b) = map(int, input().split())
	s = input()
	arr = [0] * a
	c = 0
	for i in range(1, a):
		if s[i - 1] != s[i]:
			c += 1
			arr[i] = c
		else:
			arr[i] = c
	arr[0] = 0
	for i in range(a - 1, -1, -1):
		if i - (b - 1) < 0:
			break
		ch = arr[i] - arr[i - (b - 1)]
		if s[i] == '0':
			ch += 1
		ans = min(ans, ch)
	return ans

def LCP(arr, n):
	if n == 0:
		return ''
	if n == 1:
		return arr[0]
	arr.sort()
	en = min(len(arr[0]), len(arr[n - 1]))
	fr = (arr[0], last) = arr[n - 1]
	i = 0
	while i < en and fr[i] == last(i):
		i += 1
	pre = fr.substr(0, i)
	return pre
t = int(input())
while t:
	print(solve())
	t -= 1


for g in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(cnt, ans) = (0, float('inf'))
	a = [0] * n
	for i in range(1, n):
		if s[i - 1] != s[i]:
			cnt += 1
			a[i] = cnt
		else:
			a[i] = cnt
	for i in range(n - 1, -1, -1):
		if i - (k - 1) < 0:
			break
		f = a[i] - a[i - (k - 1)]
		if s[i] == '0':
			f += 1
		ans = min(ans, f)
	print(ans)


T = int(input())
for _ in range(T):
	(N, k) = map(int, input().split(' '))
	S = input()
	(cnt, ans) = (0, float('inf'))
	arr = [0] * N
	for i in range(1, N):
		if S[i - 1] != S[i]:
			cnt += 1
			arr[i] = cnt
		else:
			arr[i] = cnt
	for i in range(N - 1, -1, -1):
		if i - (k - 1) < 0:
			break
		f = arr[i] - arr[i - (k - 1)]
		if S[i] == '0':
			f += 1
		ans = min(ans, f)
	print(ans)


def blocks(s, k):
	blk = 0
	for i in range(k):
		if i + 1 < k:
			if s[i] != s[i + 1]:
				blk += 1
	blk += 1
	return blk
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	l = []
	blok = blocks(s, k)
	for i in range(n):
		if i + k - 1 < n:
			if int(s[i + k - 1]) == 0:
				l.append(blok)
			else:
				l.append(blok - 1)
		if i + k < n:
			if s[i] != s[i + 1]:
				blok -= 1
			if s[i + k - 1] != s[i + k]:
				blok += 1
	print(min(l))


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = n
	count = 0
	for i in range(0, k - 1):
		if s[i] != s[i + 1]:
			count += 1
	if s[k - 1] == '0':
		ans = min(ans, count + 1)
	else:
		ans = min(ans, count)
	for i in range(k - 1, n - 1):
		if s[i] != s[i + 1]:
			count += 1
		if s[i - k + 1] != s[i - k + 2]:
			count -= 1
		if s[i + 1] == '0':
			ans = min(ans, count + 1)
		else:
			ans = min(ans, count)
	if s[n - 1] == '0':
		ans = min(ans, count + 1)
	else:
		ans = min(ans, count)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	segment = 1
	mini = n
	for i in range(1, k):
		if s[i] != s[i - 1]:
			segment += 1
	if s[k - 1] == '0':
		mini = min(segment, mini)
	else:
		mini = min(segment - 1, mini)
	l = 1
	for r in range(k, n):
		if s[l] != s[l - 1]:
			segment -= 1
		if s[r] != s[r - 1]:
			segment += 1
		if s[r] == '0':
			mini = min(segment, mini)
		else:
			mini = min(segment - 1, mini)
		l += 1
	print(mini)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = n
	blocks = 1
	for i in range(1, k):
		blocks += s[i] != s[i - 1]
	if s[k - 1] == '1':
		ans = blocks - 1
	else:
		ans = blocks
	for i in range(k, n):
		blocks += s[i] != s[i - 1]
		blocks -= s[i - k] != s[i - k + 1]
		if s[i] == '1':
			ans = min(ans, blocks - 1)
		else:
			ans = min(ans, blocks)
	print(ans)


test = int(input())
for _ in range(test):
	(n, k) = map(int, input().split())
	s = input()
	arr = [0 for i in range(n)]
	cn = 0
	x = 999999
	for i in range(1, n):
		if s[i - 1] != s[i]:
			cn += 1
			arr[i] = cn
		else:
			arr[i] = cn
	arr[0] = 0
	for i in range(n - 1, -1, -1):
		if i - (k - 1) < 0:
			break
		f = arr[i] - arr[i - (k - 1)]
		if s[i] == '0':
			f += 1
		x = min(x, f)
	print(x)


import sys
next((f := sys.stdin))
for (k, s) in zip(f, f):
	k = int(k.split()[1])
	r = 2 * s.count('10', 0, k) + (s[0] == '0')
	t = r - (s[k - 1] == '0')
	for (u, v, x, y) in zip(s, s[1:], s[k - 1:], s[k:-1]):
		t += (x != y) - (u != v)
		r = min(r, t + (y == '0'))
	print(r)


def sss(arr, x):
	n = len(arr)
	curr_sum = 0
	start = 0
	end = 0
	while end < n:
		while curr_sum < x and end < n:
			curr_sum += arr[end]
			end += 1
		while curr_sum - arr[start] >= x and start <= end:
			curr_sum -= arr[start]
			start += 1
		if curr_sum >= x:
			yield (start, end - start)
		if start < end:
			curr_sum -= arr[start]
			start += 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	counts = []
	z_or_o = []
	z = s[0] == '0'
	count = 0
	for a in s:
		if a == '0' and z:
			count += 1
		elif a == '1' and (not z):
			count += 1
		else:
			counts.append(count)
			if z:
				z_or_o.append(True)
			else:
				z_or_o.append(False)
			count = 1
			z = not z
	counts.append(count)
	if z:
		z_or_o.append(True)
	else:
		z_or_o.append(False)
	costs = []
	for (start, l) in sss(counts, k):
		cost = l - 1
		if z_or_o[start + l - 1]:
			cost += 1
		costs.append(cost)
	print(min(costs))


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	s = [int(i) for i in input()]
	(lt, rt) = (-1, 0)
	ans = 1000000000000000.0
	win = 0
	while rt < n:
		if lt >= 0 and s[lt] != s[lt + 1]:
			win -= 1
		if rt > 0 and s[rt] != s[rt - 1]:
			win += 1
		rt += 1
		if rt - lt > k:
			lt += 1
			if rt - lt == k:
				ans = min(ans, win + int(s[rt - 1] == 0))
	print(ans)


import sys
next((f := sys.stdin))
for (k, s) in zip(f, f):
	k = int(k.split()[1])
	s = s[:-1]
	p = sum((x != y for (x, y) in zip(s, s[1:k])))
	r = p + (s[k - 1] == '0')
	for (u, v, x, y) in zip(s, s[1:], s[k - 1:], s[k:]):
		p += (x != y) - (u != v)
		r = min(r, p + (y == '0'))
	print(r)


import sys
next((f := sys.stdin))
for (t, s) in zip(f, f):
	(n, k) = map(int, t.split())
	t = s.count('01', 0, k) + s.count('10', 0, k)
	r = t + (s[k - 1] == '0')
	for i in range(k, n):
		t += (s[i - 1] != s[i]) - (s[i - k] != s[i - k + 1])
		r = min(r, t + (s[i] == '0'))
	print(r)


t = int(input())
while t:
	t -= 1
	(res, count) = (2147483647, 0)
	(k, n) = list(map(int, input().split()))
	s = input()
	arr = [0] * k
	for i in range(1, k):
		if s[i - 1] != s[i]:
			count += 1
			arr[i] = count
		else:
			arr[i] = count
	arr[0] = 0
	for i in range(k - 1, -1, -1):
		if i - (n - 1) < 0:
			break
		cross = arr[i] - arr[i - n + 1]
		if s[i] == '0':
			cross += 1
		res = min(res, cross)
	print(res)


import sys
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	ans = sys.maxsize
	arr = []
	arr.append(0)
	for i in range(1, n):
		if s[i - 1] != s[i]:
			count += 1
			arr.append(count)
		else:
			arr.append(count)
	for i in range(n - 1, -1, -1):
		if i - (k - 1) < 0:
			break
		check = arr[i] - arr[i - k + 1]
		if s[i] == '0':
			check += 1
		ans = min(ans, check)
	print(ans)


import sys

def input():
	return sys.stdin.readline().strip()

def print(n):
	return sys.stdout.write(str(n) + '\n')
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	s = input()
	a = [0] * n
	mx = 9223372036854775807
	ct = 0
	for i in range(1, n):
		if s[i - 1] == s[i]:
			a[i] = ct
		else:
			ct += 1
			a[i] = ct
	a[0] = 0
	ans = ''
	for i in range(1, n, 2):
		ans += s[i]
	ans = ans[::-1]
	for i in range(n - 1, -1, -1):
		if i - (k - 1) < 0:
			ans = ans[:-1]
			break
		ct2 = a[i] - a[i - (k - 1)]
		if s[i] == '0':
			ans = ans[:-1]
			ct2 += 1
		mx = min(mx, ct2)
	print(mx)


import sys
t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	string = input()
	d = {0: 0}
	c = 0
	sol = sys.maxsize
	for i in range(1, n):
		if string[i - 1] != string[i]:
			c += 1
			d[i] = c
		else:
			d[i] = c
	for i in range(n - 1, -1, -1):
		if i - (k - 1) < 0:
			break
		p = i - k + 1
		h = abs(d[i] - d[p])
		if string[i] == '0':
			h += 1
		sol = min(sol, h)
	print(sol)


def isPalindrome(str):
	for i in range(0, int(len(str) / 2)):
		if str[i] != str[len(str) - i - 1]:
			return False
	return True

def findans(arr, n, k, s):
	g = 0
	ans = 100000000
	for i in range(n - 1, -1, -1):
		if i - (k - 1) < 0:
			break
		tp = arr[i] - arr[i - k + 1]
		if s[i] == '0':
			tp += 1
		ans = min(ans, tp)
	return ans

def lps(seq, i, j):
	if i == j:
		return 1
	if seq[i] == seq[j] and i + 1 == j:
		return 2
	if seq[i] == seq[j]:
		return lps(seq, i + 1, j - 1) + 2
	return max(lps(seq, i, j - 1), lps(seq, i + 1, j))
t = int(input())
while t > 0:
	lst = [int(x) for x in input().split()]
	n = lst[0]
	k = lst[1]
	s = input()
	lst2 = []
	c = 0
	lst2.append(0)
	for i in range(1, n):
		if s[i - 1] == s[i]:
			pass
		else:
			c = c + 1
		lst2.append(c)
	ans = findans(lst2, n, k, s)
	print(ans)
	t = t - 1


t = int(input())
for _ in range(t):
	(N, K) = map(int, input().split())
	S = str(input())
	value = []
	g = 1000000
	i = K - 1
	c = 0
	while i > 0:
		if S[i - 1] != S[i]:
			c = c + 1
		i = i - 1
	if S[K - 1] == '0':
		c = c + 1
	g = c
	i = K - 1
	while i < N - 1:
		if S[i + 1] != S[i] and S[i + 1] == '0':
			c = c + 2
		if S[i - K + 1] != S[i - K + 2]:
			c = c - 1
		if g > c:
			g = c
		i = i + 1
	print(g)


t = int(input())
while t:
	(a, b) = list(map(int, input().split()))
	s = input()
	result = float('inf')
	arr = [0] * a
	count = 0
	for i in range(1, a):
		if s[i - 1] != s[i]:
			count += 1
			arr[i] = count
		else:
			arr[i] = count
	for i in range(a - 1, -1, -1):
		if i - (b - 1) < 0:
			break
		check = arr[i] - arr[i - b + 1]
		if s[i] == '0':
			check += 1
		result = min(check, result)
	print(result)
	t -= 1


from sys import stdin, stdout
t = int(stdin.readline())
for _ in range(0, t):
	(n, k) = list(map(int, stdin.readline().split()))
	s = stdin.readline()
	s = s[::-1]
	s = s.replace('\n', '')
	a = [0]
	count = 0
	res = n
	for x in range(0, len(s) - 1):
		if s[x] != s[x + 1]:
			count += 1
		a.append(count)
	for i in range(n - k + 1):
		ans = a[i + k - 1] - a[i]
		if s[i] == '0':
			ans += 1
		res = min(res, ans)
	print(res)


T = int(input())
for ___ in range(T):
	(a, b) = map(int, input().split())
	s = input()
	x = list()
	res = 3 * 10 ** 5
	c = 0
	x.append(0)
	for i in range(1, a):
		if s[i - 1] != s[i]:
			c += 1
			x.append(c)
		else:
			x.append(c)
	for i in range(a - 1, -1, -1):
		if i - (b - 1) < 0:
			break
		ch = x[i] - x[i - b + 1]
		if s[i] == '0':
			ch += 1
		res = min(res, ch)
	print(res)


for _ in range(int(input())):
	(k, n) = map(int, input().split())
	st = input()
	(cnt, arr, an) = (0, [0], float('inf'))
	for i in range(1, k):
		if st[i - 1] != st[i]:
			cnt += 1
			arr.append(cnt)
		else:
			arr.append(cnt)
	for j in range(k - 1, -1, -1):
		if j - (n - 1) < 0:
			break
		ischeck = arr[j] - arr[j - n + 1]
		if st[j] == '0':
			ischeck += 1
		an = min(an, ischeck)
	print(an)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	a = [0] * n
	(cnt, ans) = (0, 1000000000.0)
	for i in range(1, n):
		if s[i - 1] != s[i]:
			cnt += 1
		a[i] = cnt
	for i in reversed(range(n)):
		if i - k + 1 < 0:
			break
		if s[i] == '0':
			tmp = a[i] - a[i - k + 1] + 1
		else:
			tmp = a[i] - a[i - k + 1]
		ans = min(ans, tmp)
	print(ans)


def solve():
	(n, k) = list(map(int, input().split()))
	s = input()
	ans = float('inf')
	arr = [0] * n
	count = 0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			count += 1
			arr[i] = count
		else:
			arr[i] = count
	for i in range(n - 1, -1, -1):
		if i - (k - 1) < 0:
			break
		check = arr[i] - arr[i - k + 1]
		if s[i] == '0':
			check += 1
		ans = min(check, ans)
	print(ans)
t = int(input())
while t:
	solve()
	t -= 1


from collections import defaultdict
import math as mt
for _ in range(int(input())):
	(n, k) = (int(i) for i in input().split())
	s = input()
	i = 0
	j = 0
	ans = int(1000000000.0)
	cnt = 0
	if k == 1:
		flag = False
		for i in range(n):
			if s[i] == '1':
				flag = True
				break
		if flag:
			print(0)
		else:
			print(1)
	else:
		while j < n:
			if j - i + 1 < k:
				if j == 0 and s[j] == '0':
					cnt += 1
				elif s[j - 1] == '1' and s[j] == '0':
					cnt += 2
				j += 1
			else:
				if s[j] == '0' and s[j - 1] == '1':
					cnt += 2
				ans = min(ans, cnt)
				if s[i] != s[i + 1]:
					cnt -= 1
				i += 1
				j += 1
		print(ans)


import sys
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	arr = [None] * a
	s = input()
	ans = a
	count = 0
	for i in range(1, a):
		if s[i - 1] != s[i]:
			count += 1
			arr[i] = count
		else:
			arr[i] = count
	arr[0] = 0
	i = a - 1
	while i >= 0:
		if i - (b - 1) < 0:
			break
		check = arr[i] - arr[i - b + 1]
		if s[i] == '0':
			check += 1
		ans = min(ans, check)
		i -= 1
	print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = str(input())
	ans = 1000000000000000.0
	c = 0
	A = [0]
	for i in range(1, N):
		if S[i - 1] != S[i]:
			c += 1
		A.append(c)
	for i in range(N - 1, -1, -1):
		if i - K + 1 < 0:
			break
		check = A[i] - A[i - K + 1]
		if S[i] == '0':
			check += 1
		ans = min(ans, check)
	print(ans)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	s = input()
	ans = 2 ** 90
	c = 0
	l = [0] * a
	for i in range(1, a):
		if s[i - 1] != s[i]:
			c += 1
			l[i] = c
		else:
			l[i] = c
	l[0] = 0
	for i in range(a - 1, -1, -1):
		if i - (b - 1) < 0:
			break
		f = l[i] - l[i - b + 1]
		if s[i] == '0':
			f += 1
		ans = min(ans, f)
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = math.inf
	arr = [0] * n
	t = 0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			t += 1
			arr[i] = t
		else:
			arr[i] = t
	arr[0] = 0
	for i in range(n - 1, -1, -1):
		if i - (k - 1) < 0:
			break
		c = arr[i] - arr[i - k + 1]
		if s[i] == '0':
			c += 1
		ans = min(ans, c)
	print(ans)


import sys
t = int(input())
while t > 0:
	(n, k) = [int(x) for x in input().split()]
	ans = sys.maxsize
	s = input()
	arr = [0] * n
	c = 0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			c += 1
			arr[i] = c
		else:
			arr[i] = c
	arr[0] = 0
	for i in range(n - 1, -1, -1):
		if i - (k - 1) < 0:
			break
		check = arr[i] - arr[i - (k - 1)]
		if s[i] == '0':
			check += 1
		ans = min(ans, check)
	print(ans)
	t = t - 1


def prints(a):
	for i in range(len(a)):
		print(a[i], end=' ')
	print()

def rrr(a):
	f = 0
	for i in range(len(a)):
		if a.count(a[i]) < a[i]:
			f = 1
			break
	return f
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	l = [0]
	ll = 1000000.0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			c += 1
			l.append(c)
		else:
			l.append(c)
	p = []
	for i in range(n - 1, -1, -1):
		if i < k - 1:
			break
		c = l[i] - l[i + 1 - k]
		if s[i] != '1':
			c += 1
		ll = min(ll, c)
	print(ll)


import sys

def sol(n, k):
	s = input()
	f = 0
	r = 0
	ans = 0
	max1 = 9223372036854775807
	while r < k - 1 and r < n - 1:
		if s[r] != s[r + 1]:
			ans += 1
		r += 1
	for i in range(k - 1, n):
		if i != k - 1:
			x = i - k
			if s[x] != s[x + 1]:
				ans -= 1
			if s[i] == '0':
				y = 1
			else:
				y = 0
			max1 = min(max1, ans + y)
			if i < n - 1:
				if s[i] != s[i + 1]:
					ans += 1
		else:
			if s[i] == '0':
				y = 1
			else:
				y = 0
			max1 = min(max1, ans + y)
			if i < n - 1:
				if s[i] != s[i + 1]:
					ans += 1
	print(max1)
t = int(input())
for temp in range(t):
	(n, k) = map(int, input().split())
	sol(n, k)


def min_operations(S, N, K):
	ans = 9999999999
	arr = [0] * N
	count = 0
	for i in range(1, N):
		if S[i - 1] != S[i]:
			count += 1
			arr[i] = count
		else:
			arr[i] = count
	arr[0] = 0
	for i in range(N - 1, -1, -1):
		if i - (K - 1) < 0:
			break
		check = arr[i] - arr[i - (K - 1)]
		if S[i] == '0':
			check += 1
		ans = min(ans, check)
	return ans
t = int(input())
while t > 0:
	(x, y) = input().split(' ')
	x = int(x)
	y = int(y)
	str1 = input()
	print(min_operations(str1, x, y))
	t -= 1


t = int(input())
for x in range(0, t):
	(n, k) = map(int, input().split())
	s = input()
	f = 0
	r = 0
	ans = 0
	man = float('inf')
	while r < k - 1 and r < n - 1:
		if s[r] != s[r + 1]:
			ans += 1
		r += 1
	for i in range(k - 1, n):
		if i != k - 1:
			x = i - k
			if s[x] != s[x + 1]:
				ans -= 1
			y = 1 - int(ord(s[i]) - ord('0'))
			man = min(man, ans + y)
			if i < n - 1:
				if s[i] != s[i + 1]:
					ans += 1
		else:
			y = 1 - int(ord(s[i]) - ord('0'))
			man = min(man, ans + y)
			if i < n - 1:
				if s[i] != s[i + 1]:
					ans += 1
	print(man)


t = int(input())
while t:
	(A, B) = map(int, input().split())
	str = input()
	arr = [0] * A
	count = 0
	for i in range(1, A):
		if str[i - 1] != str[i]:
			count += 1
			arr[i] = count
		else:
			arr[i] = count
	ANS = float('inf')
	for i in range(A - 1, -1, -1):
		if i - (B - 1) < 0:
			break
		check = arr[i] - arr[i - B + 1]
		if str[i] == '0':
			check += 1
		ANS = min(ANS, check)
	print(ANS)
	t -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = input()
	ans = 10 ** 7 + 1
	arr = [0] * a
	cnt = 0
	for i in range(1, a):
		if s[i - 1] != s[i]:
			cnt += 1
			arr[i] = cnt
		else:
			arr[i] = cnt
	arr[0] = 0
	for i in range(a - 1, -1, -1):
		if i - (b - 1) < 0:
			break
		check = arr[i] - arr[i - b + 1]
		if s[i] == '0':
			check += 1
		ans = min(ans, check)
	print(ans)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(f, r, ans) = (0, 0, 0)
	man = 3 * 10 ** 5
	while r < k - 1 and r < n - 1:
		if s[r] != s[r + 1]:
			ans += 1
		r += 1
	for i in range(k - 1, n):
		if i != k - 1:
			x = i - k
			if s[x] != s[x + 1]:
				ans -= 1
			y = 1 - int(s[i])
			man = min(man, ans + y)
			if i < n - 1:
				if s[i] != s[i + 1]:
					ans += 1
		else:
			y = 1 - int(s[i])
			man = min(man, ans + y)
			if i < n - 1:
				if s[i] != s[i + 1]:
					ans += 1
	print(man)


for t in range(int(input())):
	(a, b) = map(int, input().split())
	string = input()
	array = [0] * a
	count = 0
	minimum = 1000000
	for i in range(1, a):
		if string[i - 1] != string[i]:
			count += 1
			array[i] = count
		else:
			array[i] = count
	for i in range(a - 1, -1, -1):
		if i - (b - 1) < 0:
			break
		x = array[i] - array[i - (b - 1)]
		if string[i] == '0':
			x += 1
		minimum = min(minimum, x)
	print(minimum)


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	s = input()
	ans = float('inf')
	count = 0
	arr = [0] * a
	for i in range(1, a):
		if s[i - 1] != s[i]:
			count += 1
			arr[i] = count
		else:
			arr[i] = count
	for i in range(a - 1, -1, -1):
		if i - (b - 1) < 0:
			break
		check = arr[i] - arr[i - b + 1]
		if s[i] == '0':
			check += 1
		ans = min(ans, check)
	print(ans)


import sys
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = [0] * n
	c = 0
	a = sys.maxsize
	for i in range(1, n):
		if s[i - 1] != s[i]:
			c += 1
			l[i] = c
		else:
			l[i] = c
	l[0] = 0
	for j in range(n - 1, -1, -1):
		if j - (k - 1) < 0:
			break
		z = l[j] - l[j - (k - 1)]
		if s[j] == '0':
			z += 1
		a = min(a, z)
	print(min(a, z))