On each of the following $N$ days (numbered $1$ through $N$), Chef is planning to cook either pizza or broccoli. He wrote down a string $A$ with length $N$, where for each valid $i$, if the character $A_i$ is '1', then he will cook pizza on the $i$-th day, while if $A_i$ is '0', he will cook broccoli on this day.
Chefu, his son, loves pizza but hates broccoli ― just like most kids. He wants to select a substring of $A$ with length $K$ and change each character '0' in this substring to '1'. Afterwards, let's define pizza time as the maximum number of consecutive days where Chef will cook pizza. Find the maximum pizza time Chefu can achieve.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$. 
- The second line contains a string $A$ with length $N$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum pizza time.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le K \le N \le 10^5$
- $A$ contains only characters '0' and '1'
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points):
- $N \le 10^3$
- the sum of $N$ over all test cases does not exceed $10^4$
Subtask #2 (50 points): original constraints

-----Example Input-----
2
13 2
0101110000101
6 3
100001

-----Example Output-----
5
4

-----Explanation-----
Example case 1: Chefu can choose the substring $A[2, 3]$ = "10", and change the third character of $A$ to '1'. Then, the pizza time is $5$ days: from day $2$ to day $6$.
Example case 2: Chefu can choose the substring $A[2, 4]$ = "000". Then, the pizza time is $4$ days: from day $1$ to day $4$.

Difficulty: HARD
Tags: String algorithms

Data structures

Amortized analysis

Greedy algorithms
Skill types: Amortized analysis

Data structures

Greedy algorithms

Starter code:

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


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input()]
	index = k - 1
	start = 0
	res = 0
	while index < n:
		tmp_res = k
		tmp_index = index
		while tmp_index + 1 < n and arr[tmp_index + 1] == 1:
			tmp_res += 1
			tmp_index += 1
		tmp_index = start
		while tmp_index - 1 >= 0 and arr[tmp_index - 1] == 1:
			tmp_res += 1
			tmp_index -= 1
		res = max(res, tmp_res)
		index += 1
		start += 1
	print(res)


def solve(n, k, s):
	l = [None] * (n + 1)
	l[0] = 0
	for i in range(n):
		if int(s[i]):
			l[i + 1] = l[i] + 1
		else:
			l[i + 1] = 0
	r = [None] * (n + 1)
	r[n] = 0
	for i in reversed(range(n)):
		if int(s[i]):
			r[i] = r[i + 1] + 1
		else:
			r[i] = 0
	ans = 0
	for i in range(n - k + 1):
		ans = max(ans, l[i] + k + r[i + k])
	return ans

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		s = input()
		print(solve(n, k, s))
main()


strng = lambda : input()
inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
slst = lambda : list(input().split()[0])
silst = lambda : list(map(int, input().split()[0]))
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
import sys
input = sys.stdin.readline
from collections import defaultdict
from math import ceil, log, floor, sqrt, gcd, log10

def merge(a, lo, hi, m):
	tmp = []
	i = lo
	j = m + 1
	while i <= m and j <= hi:
		if a[i] > a[j]:
			tmp += [a[j]]
			j += 1
		else:
			tmp += [a[i]]
			i += 1
	while i <= m:
		tmp += [a[i]]
		i += 1
	while j <= hi:
		tmp += [a[j]]
		j += 1
	j = 0
	for i in range(lo, hi + 1):
		a[i] = tmp[j]
		j += 1

def msrt(arr, lo, hi):
	if lo < hi:
		m = (lo + hi) // 2
		msrt(arr, lo, m)
		msrt(arr, m + 1, hi)
		merge(arr, lo, hi, m)
for _ in range(inp()):
	(n, k) = mul()
	arr = input()
	prefix = [0] * n
	suffix = [0] * n
	(i, j) = (0, 1)
	flag = arr[0] != '0'
	while i < n and j < n:
		if not flag and arr[j] == '1':
			i = j
			flag = True
		elif flag and arr[j] == '0':
			idx = 1
			while i < j:
				suffix[i] = j - i
				prefix[i] = idx
				idx += 1
				i += 1
			flag = False
		j += 1
	diff = j - i
	idx = 1
	while i < j and flag:
		prefix[i] = idx
		suffix[i] = j - i
		idx += 1
		i += 1
	max_len = k + suffix[k] if k < n else k
	for i in range(1, n - k):
		length = k + prefix[i - 1] + suffix[i + k]
		max_len = max(length, max_len)
	if n - k - 1 >= 0:
		max_len = max(prefix[n - k - 1] + k, max_len)
	print(max_len)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	head = [0] * n
	tail = [0] * n
	for i in range(1, n):
		if s[i - 1] == '0':
			head[i] = 0
		else:
			head[i] = head[i - 1] + 1
	for i in range(n - 2, -1, -1):
		if s[i + 1] == '0':
			tail[i] = 0
		else:
			tail[i] = tail[i + 1] + 1
	result = []
	for i in range(n - k + 1):
		x = head[i] + k + tail[i + k - 1]
		result.append(x)
	print(max(result))


t = int(input())
for _ in range(t):
	(n, k) = (int(x) for x in input().split())
	as_ = [int(x) for x in input()]
	assert len(as_) == n
	left_streak = [0]
	ct_left = 0
	for ii in as_[:n - k]:
		ct_left += 1
		if ii == 0:
			ct_left = 0
		left_streak.append(ct_left)
	right_streak = [0]
	ct_right = 0
	for ii in reversed(as_[k:]):
		ct_right += 1
		if ii == 0:
			ct_right = 0
		right_streak.append(ct_right)
	print(max((x + y + k for (x, y) in zip(left_streak, reversed(right_streak)))))


def pizzaOrBroc(n, k, a):
	L = [0] * n
	R = [0] * n
	maxpizza = 0
	for i in range(1, n):
		if int(a[i - 1]) == 1:
			L[i] = L[i - 1] + 1
	for i in range(n - 2, -1, -1):
		if int(a[i + 1]) == 1:
			R[i] = R[i + 1] + 1
	for i in range(0, n - k + 1):
		maxpizza = max(maxpizza, L[i] + k + R[i + k - 1])
	return maxpizza
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	temp = input()
	a = list(temp)
	print(pizzaOrBroc(n, k, a))


N_cases = int(input())
for case in range(N_cases):
	(N, K) = [int(n) for n in input().split(' ')]
	A = input()
	patches = N - K + 1
	pizza_time = 0
	for i in range(patches):
		cprev = 0
		cpost = 0
		c = 1
		while True and i - c >= 0:
			if A[i - c] == '1':
				cprev = cprev + 1
			else:
				break
			c = c + 1
		c = 0
		while True and i + c <= N - K - 1:
			if A[i + K + c] == '1':
				cpost = cpost + 1
			else:
				break
			c = c + 1
		pizza_time_new = K + cpost + cprev
		if pizza_time_new > pizza_time:
			pizza_time = pizza_time_new
	print(pizza_time)


def fun(li, k):
	head = [0] * len(li)
	tail = [0] * len(li)
	for i in range(1, len(li)):
		if li[i - 1] == '1':
			head[i] = head[i - 1] + 1
		else:
			head[i] = 0
	for i in range(len(li) - 2, -1, -1):
		if li[i + 1] == '1':
			tail[i] = tail[i + 1] + 1
		else:
			tail[i] = 0
	ans = 0
	for i in range(0, len(li) - k + 1):
		ans = max(ans, k + head[i] + tail[i + k - 1])
	return ans
t = int(input())
for i in range(0, t):
	s = list(map(int, input().strip().split()))
	s1 = s[0]
	s2 = s[1]
	li = input()
	print(fun(li, s2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = input()
	pre = [0] * n
	suf = [0] * n
	(i, j) = (0, 1)
	flag = arr[0] != '0'
	while i < n and j < n:
		if not flag and arr[j] == '1':
			i = j
			flag = True
		elif flag and arr[j] == '0':
			ix = 1
			while i < j:
				suf[i] = j - i
				pre[i] = ix
				ix += 1
				i += 1
			flag = False
		j += 1
	diff = j - i
	ix = 1
	while i < j and flag:
		pre[i] = ix
		suf[i] = j - i
		ix += 1
		i += 1
	ml = k + suf[k] if k < n else k
	for i in range(1, n - k):
		length = k + pre[i - 1] + suf[i + k]
		ml = max(length, ml)
	if n - k - 1 >= 0:
		ml = max(pre[n - k - 1] + k, ml)
	print(ml)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = input()
	a = [int(i) for i in a]
	ans = k
	for i in range(n - k + 1):
		c = k
		j = i + k
		while j < n and a[j] == 1:
			c += 1
			j += 1
		j = i - 1
		while j >= 0 and a[j] == 1:
			c += 1
			j -= 1
		ans = max(ans, c)
	print(ans)


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	arr = input()
	x = 0
	y = 0
	left = []
	right = [0] * n
	for i in range(0, n):
		left.append(x)
		if arr[i] == '1':
			x = x + 1
		else:
			x = 0
	for i in range(n - 1, -1, -1):
		right[i] = y
		if arr[i] == '1':
			y = y + 1
		else:
			y = 0
	ans = 0
	for i in range(0, n):
		if i + k - 1 < n:
			max_ = left[i] + k + right[i + k - 1]
		else:
			max_ = left[i] + n - i
		if max_ > ans:
			ans = max_
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, list(input())))
	right = [0] * (n + 1)
	count = 0
	for i in range(n - 1, -1, -1):
		if arr[i] == 1:
			count += 1
		else:
			count = 0
		right[i] = count
	count = 0
	ans = 0
	for i in range(n):
		length = 0
		length = count + (min(i + k, n) - i) + right[min(i + k, n)]
		ans = max(ans, length)
		if arr[i] == 1:
			count += 1
		else:
			count = 0
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	heads = [0 for i in range(n)]
	tails = [0 for i in range(n)]
	heads[0] = 0
	for i in range(1, n):
		if a[i - 1] == '1':
			heads[i] = heads[i - 1] + 1
		else:
			heads[i] = 0
	tails[-1] = 0
	for i in range(n - 2, -1, -1):
		if a[i + 1] == '1':
			tails[i] = tails[i + 1] + 1
		else:
			tails[i] = 0
	maxones = 0
	i = 0
	while i + k <= n:
		maxones = max(maxones, heads[i] + k + tails[i + k - 1])
		i += 1
	print(maxones)


def solve(arr, n, k):
	D = [0] * (n + 1)
	D[n] = 0
	for i in range(n - 1, -1, -1):
		if arr[i] == 1:
			D[i] = D[i + 1] + 1
		else:
			D[i] = 0
	I = [0] * (n + 1)
	I[0] = 0
	for i in range(1, n + 1):
		if arr[i - 1] == 1:
			I[i] = I[i - 1] + 1
		else:
			I[i] = 0
	lbs = 0
	for i in range(k, n + 1):
		if lbs < D[i] + k + I[i - k]:
			lbs = D[i] + k + I[i - k]
	lbs = max(lbs, max(D), k)
	return lbs
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, list(input().strip())))
	print(solve(arr, n, k))


num = int(input())
t = 0
while t < num:
	(n, k) = map(int, input().split())
	s = str(input())
	count = 0
	pos = []
	for i in range(n):
		if s[i] == '0':
			pos.append(i)
	for i in range(len(pos)):
		ind = pos[i]
		val = 0
		if ind - k + 1 < 0:
			val += ind + 1
		else:
			val += k
			bn = ind - k
			while bn >= 0:
				if s[bn] == '1':
					val += 1
				else:
					break
				bn -= 1
		if i != len(pos) - 1:
			val += pos[i + 1] - pos[i] - 1
		else:
			ui = 0
			gh = pos[len(pos) - 1] + 1
			while gh < n:
				if s[gh] == '1':
					ui += 1
				gh += 1
			val += ui
		if val > count:
			count = val
	if len(pos) == 0:
		print(n)
	else:
		print(count)
	t += 1


def pizzatime(s, a, k):
	(cont1, m_time) = (0, 0)
	for i in range(len(s)):
		if s[i] == '1':
			cont1 += 1
		else:
			try:
				m_time = max(m_time, cont1 + k + a[i + k])
			except:
				m_time = max(m_time, cont1 + min(k, len(s) - i))
			cont1 = 0
	m_time = max(m_time, cont1)
	return m_time
for T in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	all_1 = [0] * (n + 1)
	check = True
	for ind in range(len(s) - 1, -1, -1):
		if s[ind] == '1':
			all_1[ind] += all_1[ind + 1] + 1
	print(pizzatime(s, all_1, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	head = [0] * len(s)
	tail = [0] * len(s)
	for i in range(1, len(s)):
		if s[i - 1] == '0':
			head[i] = 0
		else:
			head[i] = head[i - 1] + 1
	for i in range(n - 2, -1, -1):
		if s[i + 1] == '0':
			tail[i] = 0
		else:
			tail[i] = tail[i + 1] + 1
	ans = 0
	for i in range(0, len(s) - k + 1):
		ans = max(ans, k + head[i] + tail[i + k - 1])
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = str(input())
	m = 0
	for i in range(n - k + 1):
		count = k
		j = i - 1
		while j > -1 and j < n:
			if arr[j] == '1':
				count += 1
				j -= 1
			else:
				break
		l = i + k
		while l < n and l > -1:
			if arr[l] == '1':
				count += 1
				l += 1
			else:
				break
		if count > m:
			m = count
	print(m)


t = int(input())
for T in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	(l, r) = ([0] * n, [0] * n)
	for i in range(1, n):
		if s[i - 1] == '1':
			l[i] = l[i - 1] + 1
	for i in range(n - 2, -1, -1):
		if s[i + 1] == '1':
			r[i] = r[i + 1] + 1
	ans = 0
	for i in range(n - k + 1):
		ans = max(ans, l[i] + k + r[i + k - 1])
	print(ans)


def solve(arr, n, k):
	lbs = 0
	for i in range(0, n - k + 1):
		cnt = k
		for j in range(i - 1, -1, -1):
			if arr[j] == 1:
				cnt += 1
			else:
				break
		for j in range(i + k, n):
			if arr[j] == 1:
				cnt += 1
			else:
				break
		lbs = max(lbs, cnt)
	return lbs
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, list(input().strip())))
	print(solve(arr, n, k))


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	S = input()
	left = [0] * N
	right = [0] * N
	left[0] = 1 * (S[0] == '1')
	right[-1] = 1 * (S[-1] == '1')
	for i in range(1, N):
		if S[i] == '1':
			left[i] = left[i - 1] + 1
		else:
			left[i] = 0
	for i in range(N - 2, 0, -1):
		if S[i] == '1':
			right[i] = right[i + 1] + 1
		else:
			right[i] = 0
	ans = K
	for i in range(N - 1, K - 2, -1):
		x = 0
		y = 0
		if left[i - (K - 1)] == 0:
			if i - K >= 0 and left[i - K]:
				x = left[i - K]
		else:
			x = left[i - (K - 1)] - 1
		if right[i] == 0:
			if i + 1 < N and right[i + 1]:
				y = right[i + 1]
		else:
			y = right[i] - 1
		ans = max(ans, K + x + y)
	print(ans)


def solve():
	(N, K) = map(int, input().split())
	S = input()
	eleje = [0 for i in range(N)]
	vege = [0 for i in range(N)]
	if S[0] == '1':
		vege[0] = 1
	for i in range(1, N):
		if S[i] == '1':
			vege[i] = vege[i - 1] + 1
		else:
			vege[i] = 0
	if S[N - 1] == '1':
		eleje[N - 1] = 1
	for i in range(N - 2, -1, -1):
		if S[i] == '1':
			eleje[i] = eleje[i + 1] + 1
		else:
			eleje[i] = 0
	ans = -1
	for i in range(N - K + 1):
		j = i + K - 1
		a = K
		if i - 1 >= 0:
			a += vege[i - 1]
		if j + 1 < N:
			a += eleje[j + 1]
		ans = max(ans, a)
	print(ans)

def main():
	T = int(input())
	while T > 0:
		solve()
		T = T - 1
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [*map(int, input())]
	count = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		if l[i] == 1:
			count[i] = count[i + 1] + 1
	(x, y) = (0, 0)
	for i in range(n):
		if l[i] == 1:
			x += 1
		else:
			try:
				y = max(y, x + k + count[i + k])
			except:
				y = max(y, x + min(k, n - i))
			x = 0
		y = max(y, x)
	print(y)


def pizza_time(aing, king, ping, ning):
	return (aing.index('0', ping + king) if '0' in aing[ping + king:] else ning) - (aing.rindex('0', 0, ping) + 1 if '0' in aing[:ping] else 0)
for ing in range(int(input())):
	(ning, king) = map(int, input().split())
	aing = input()[:ning]
	if not '0' in aing:
		print(len(aing))
		continue
	if not '1' in aing:
		print(king)
		continue
	if len(aing) == king:
		print(king)
		continue
	print(max([pizza_time(aing, king, ing, ning) for ing in range(ning - king + 1)]))


from collections import defaultdict as dc
from collections import deque as dq
from bisect import bisect_left, bisect_right, insort_left
import sys
import math
mod = 10 ** 9 + 7

def bs(a, x):
	i = bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return len(a)

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

def line():
	p = list(map(int, input().split()))
	return p

def bs(a, b):
	l = a
	r = b + 1
	x = b
	ans = 0
	while l < r:
		mid = (l + r) // 2
		if x | mid > ans:
			ans = x | mid
			l = mid + 1
		else:
			r = mid
	return ans

def digit(n):
	a = []
	while n > 0:
		a.append(n % 10)
		n = n // 10
	return a
for _ in range(inp()):
	(n, k) = line()
	a = str(input())
	h = [0] * n
	t = [0] * n
	ans = k
	for i in range(n - 1):
		if a[i] == '1':
			h[i + 1] = h[i] + 1
		else:
			h[i + 1] = 0
	for i in range(n - 1, 0, -1):
		if a[i] == '1':
			t[i - 1] = t[i] + 1
		else:
			t[i - 1] = 0
	for i in range(n - k + 1):
		p = t[i + k - 1]
		ans = max(ans, h[i] + p + k)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(input())
	final_ans = 0
	count = 0
	for i in range(n - k + 1):
		for j in range(i + k, n):
			if arr[j] == '1':
				count += 1
			else:
				break
		m = i - 1
		while m >= 0 and i != 0:
			if arr[m] == '1':
				count += 1
			else:
				break
			m -= 1
		ans = count + k
		count = 0
		final_ans = max(ans, final_ans)
	print(final_ans)


def create(lst):
	A = []
	B = 0
	for num in lst:
		if num == 0:
			B = 0
		else:
			B += 1
		A.append(B)
	return A
T = int(input())
for _ in range(T):
	(N, K) = [int(s) for s in input().split()]
	days = [0] + [int(s) for s in input()] + [0]
	left = create(days)
	right = create(days[::-1])[::-1]
	A = 0
	for i in range(K + 1, N + 2):
		A = max(A, left[i - K - 1] + K + right[i])
	print(A)


for _ in range(int(input())):
	(n, k) = (int(x) for x in input().split())
	a = input()
	hidari = [0] * n
	migi = [0] * n
	for i in range(n - k + 1):
		loli = i
		i -= 1
		num = 0
		while i >= 0:
			if a[i] == '1':
				num += 1
				i -= 1
			else:
				break
		hidari[loli] = num
	for j in range(k - 1, n):
		kaori = j
		j += 1
		num = 0
		while j <= n - 1:
			if a[j] == '1':
				num += 1
				j += 1
			else:
				break
		migi[kaori] = num
	if n == k:
		print(n)
	else:
		max = 0
		for i in range(n - k + 1):
			if max < hidari[i] + k + migi[i + k - 1]:
				max = hidari[i] + k + migi[i + k - 1]
		print(max)


def fun(s):
	p = 0
	m = 0
	for i in range(n - 1):
		if s[i] == '1' and s[i + 1] == '1':
			p += 1
		else:
			p = 0
		m = max(m, p)
	return m + 1
for __ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	r = 0
	for i in range(n - k + 1):
		s1 = '1' * k
		h = fun(s[:i] + s1 + s[i + k:])
		r = max(r, h)
	print(r)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	left = [0 for i in range(n)]
	right = [0 for i in range(n)]
	if s[0] == '1':
		left[0] = 1
	for i in range(1, n):
		if s[i] == '1':
			left[i] = left[i - 1] + 1
	if s[-1] == '1':
		right[-1] = 1
	for i in range(n - 2, -1, -1):
		if s[i] == '1':
			right[i] = right[i + 1] + 1
	ans = k
	for i in range(n):
		temp = left[i]
		if i + k + 1 < n:
			temp += k + right[i + k + 1]
		else:
			temp += n - 1 - i
		ans = max(ans, temp)
	for i in range(n):
		temp = right[i]
		if i - k > 0:
			temp += k + left[i - k - 1]
		else:
			temp += i
		ans = max(ans, temp)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(input())
	l1 = [0] * n
	l2 = [0] * n
	for i in range(1, n):
		if l[i - 1] == '1':
			l1[i] = l1[i - 1] + 1
	for i in range(n - 2, -1, -1):
		if l[i + 1] == '1':
			l2[i] = l2[i + 1] + 1
	ans = 0
	for i in range(n - k + 1):
		ans = max(ans, l1[i] + l2[i + k - 1] + k)
	print(ans)


T = int(input())
while T > 0:
	(N, K) = [int(x) for x in input().split()]
	s = list(input())
	l = [0] * N
	r = [0] * N
	temp = 0
	for i in range(N):
		if s[i] == '1':
			temp += 1
			l[i] = temp
		else:
			temp = 0
	temp = 0
	for i in range(N - 1, -1, -1):
		if s[i] == '1':
			temp += 1
			r[i] = temp
		else:
			temp = 0
	ans = K
	for i in range(N - K + 1):
		t = K
		if i + K < N:
			t += r[i + K]
		if i > 0:
			t += l[i - 1]
		ans = max(t, ans)
	print(ans)
	T -= 1


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


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	A = ['0']
	A.extend(input())
	A.extend(['0'])
	B = [0] * (N + 2)
	C = B.copy()
	for (i, j) in enumerate(A[1:], start=1):
		if j == '1':
			B[i] = B[i - 1] + 1
	A.reverse()
	for (i, j) in enumerate(A[1:], start=1):
		if j == '1':
			C[i] = C[i - 1] + 1
	A.reverse()
	C.reverse()
	i = 1
	j = K
	ans = 0
	while j <= N:
		ans = max(ans, K + B[i - 1] + C[j + 1])
		i += 1
		j += 1
	print(ans)


te = int(input())
while te > 0:
	te -= 1
	(n, k) = list(map(int, input().split()))
	dishes = list(input())
	heads = [0] * n
	tails = [0] * n
	for i in range(1, n):
		if dishes[i - 1] == '1':
			heads[i] = heads[i - 1] + 1
		else:
			heads[i] = 0
	j = n - 2
	while j >= 0:
		if dishes[j + 1] == '1':
			tails[j] = tails[j + 1] + 1
		else:
			tails[j] = 0
		j -= 1
	ans = 0
	i = 0
	while i + k <= n:
		ans = max(ans, heads[i] + k + tails[i + k - 1])
		i += 1
	print(ans)


from typing import List

def max_consecutive_by_forcing_section(bits: str, forced_size: int) -> int:
	if bits is None or forced_size is None:
		print('max_consecutive_by_forcing_section called with missing parameters')
		return -1
	if any([b != '0' and b != '1' for b in bits]):
		print('max_consecutive_by_forcing_section called with non binary string')
	n_bits = len(bits)
	if n_bits <= forced_size:
		return n_bits
	bits = '0' + bits + '0'
	n_bits += 2
	cons_left = count_consecutive_ones(bits)
	cons_right = count_consecutive_ones(bits[::-1])
	cons_right.reverse()
	max_length = 0
	for i in range(n_bits - forced_size - 1):
		if cons_left[i] + cons_right[i + 1 + forced_size] > max_length:
			max_length = cons_left[i] + cons_right[i + 1 + forced_size]
	return max_length + forced_size

def count_consecutive_ones(bits: str) -> List[int]:
	cons = []
	for b in bits:
		if b == '1':
			count += 1
		else:
			count = 0
		cons.append(count)
	return cons

def main():
	tests = int(input())
	for _ in range(tests):
		forced_size = int(input().split()[1])
		bits = input()
		max_length = max_consecutive_by_forcing_section(bits, forced_size)
		print(max_length)
main()


for _ in range(int(input())):
	(a, k) = map(int, input().split())
	inp = [int(i) for i in input()]
	conright = list(inp)
	prev = conright[0]
	for i in range(1, a):
		if conright[i] == 1:
			if prev == 1:
				conright[i] = conright[i - 1] + 1
			else:
				prev = conright[i]
		else:
			prev = conright[i]
	conleft = list(inp)
	prev = conleft[a - 1]
	for i in range(a - 2, -1, -1):
		if conleft[i] == 1:
			if prev == 1:
				conleft[i] = conleft[i + 1] + 1
			else:
				prev = conleft[i]
		else:
			prev = conleft[i]
	conright.insert(0, 0)
	conleft.append(0)
	m = -1
	for i in range(a - k + 1):
		insr = conright[i - 1]
		insl = conleft[i + k]
		m = max(m, k + conright[i] + conleft[i + k])
	print(m)


for t in range(int(input())):
	N = input()
	A = input()
	N = N.split(' ')
	k = int(N[1])
	N = int(N[0])
	longest = 0
	max_ = k
	for i in range(0, N):
		if A[i] == '0':
			if i + k >= N:
				max_ = max(max_, longest + (N - i))
				break
			else:
				q = i + k
				while q < N and A[q] == '1':
					q += 1
				longest = longest + q - i
				max_ = max(max_, longest)
			longest = 0
		else:
			longest += 1
	print(max(max_, longest))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	st = list(input())
	ans = 0
	i = 0
	while i <= n - k:
		count = k
		for j in range(i + k, n):
			if st[j] == '1':
				count += 1
			else:
				break
		for j in range(i - 1, -1, -1):
			if st[j] == '1':
				count += 1
			else:
				break
		ans = max(ans, count)
		i += 1
	print(ans)


import math, sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
lili = lambda : list(map(int, sys.stdin.readlines()))
li = lambda : list(map(int, input().split()))
I = lambda : int(input())
S = lambda : input()
t = I()
for i in range(0, t):
	(n, k) = li()
	s = S()
	c = 0
	a = []
	for i in s[:n]:
		if i == '1':
			a.append(c)
			c += 1
		else:
			a.append(c)
			c = 0
	c = 0
	b = []
	t = s[n - 1::-1]
	for i in t:
		if i == '1':
			b.append(c)
			c += 1
		else:
			b.append(c)
			c = 0
	m = 0
	b = b[::-1]
	for i in range(0, n - k + 1):
		m = max(m, a[i] + b[i + k - 1] + k)
	print(m)


T = int(input())
for _ in range(0, T):
	(N, K) = map(int, input().split())
	S = input()
	ans = -1
	for i in range(0, N - K + 1):
		count = K
		j = i - 1
		while -1 < j < N:
			if S[j] == '1':
				count += 1
				j -= 1
			else:
				break
		k = i + K
		while -1 < k < N:
			if S[k] == '1':
				count += 1
				k += 1
			else:
				break
		ans = max(ans, count)
	print(ans)


def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		a = list(map(int, list(input())))
		i = 0
		nootn = 0
		nool = [0] * (n + 1)
		max = k
		while i <= n - k:
			if i > 0 and a[i - 1] == 1:
				nootn += 1
			else:
				nootn = 0
			if i == n - k:
				if max < nootn + k:
					max = nootn + k
					break
			if nool[i + k - 1] == 0:
				j = i + k
				while j < n and a[j] == 1:
					j += 1
				nool[i + k] = j - i - k
			else:
				nool[i + k] = nool[i + k - 1] - 1
			if max < nool[i + k] + k + nootn:
				max = nool[i + k] + k + nootn
			i += 1
		print(max)
main()


for z in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	maxl = 0
	for i in range(0, n - k + 1):
		j = i - 1
		c0 = 0
		c1 = 0
		while j >= 0:
			if s[j] == '1':
				c0 += 1
				j -= 1
			else:
				break
		j = i + k
		while j < n:
			if s[j] == '1':
				c1 += 1
				j += 1
			else:
				break
		if maxl < c0 + c1 + k:
			maxl = c0 + c1 + k
	else:
		print(maxl)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = input()
	(head, tail) = ([0] * n, [0] * n)
	for i in range(1, n):
		if l[i - 1] == '0':
			head[i] = 0
		else:
			head[i] += head[i - 1] + 1
	temp = l[::-1]
	for i in range(1, n):
		if temp[i - 1] == '0':
			tail[i] = 0
		else:
			tail[i] += tail[i - 1] + 1
	tail = tail[::-1]
	ans = head[0] + k + tail[k - 1]
	for i in range(1, n - k + 1):
		ans = max(ans, head[i] + k + tail[i + k - 1])
	print(ans)


import sys, string as strr
input = lambda : sys.stdin.readline().rstrip('\r\n')
M = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	head = [0] * len(s)
	tail = [0] * len(s)
	for i in range(1, len(s)):
		if s[i - 1] == '0':
			head[i] = 0
		else:
			head[i] = head[i - 1] + 1
	for i in range(n - 2, -1, -1):
		if s[i + 1] == '0':
			tail[i] = 0
		else:
			tail[i] = tail[i + 1] + 1
	ans = 0
	for i in range(0, len(s) - k + 1):
		ans = max(ans, k + head[i] + tail[i + k - 1])
	print(ans)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(input())
	for i in range(len(arr)):
		arr[i] = int(arr[i])
	head = [0 for i in range(n)]
	for i in range(1, n):
		if arr[i - 1] == 0:
			head[i] = 0
		elif arr[i - 1] == 1:
			head[i] = head[i - 1] + 1
	tail = [0 for i in range(n)]
	for i in range(n - 2, -1, -1):
		if arr[i + 1] == 0:
			tail[i] = 0
		elif arr[i + 1] == 1:
			tail[i] = tail[i + 1] + 1
	ans = 0
	j = 0
	while j + k <= n:
		ans = max(ans, k + head[j] + tail[j + k - 1])
		j += 1
	print(ans)


def binary_search(start, end, l, p):
	m = (start + end) // 2
	if start >= end:
		if l[start] < p:
			return start + 1
		return start
	if l[m] > p:
		return binary_search(start, m - 1, l, p)
	elif l[m] < p:
		return binary_search(m + 1, end, l, p)
	elif l[m] == p:
		return m

def f():
	(n, k) = map(int, input().split(' '))
	a = input()
	l = []
	for i in range(0, len(a)):
		if a[i] == '0':
			l.append(i)
	if len(l) == 0:
		maxi = len(a)
	else:
		maxi = 0
	for i in range(0, len(l)):
		t = l[i] + k
		t = binary_search(i, len(l) - 1, l, t)
		if i == 0:
			q = -1
		else:
			q = l[i - 1]
		if t > len(l) - 1:
			t = len(a)
			maxi = max(t - q - 1, maxi)
			break
		maxi = max(l[t] - q - 1, maxi)
	print(maxi)
for i in range(int(input())):
	f()


t = int(input())
for i in range(t):
	st = input().split()
	N = int(st[0])
	K = int(st[1])
	s = input().strip()
	F = [0] * (N + 2)
	R = [0] * (N + 2)
	p = 0
	c = 0
	for k in range(1, N + 1):
		if s[p] == '1':
			c += 1
		else:
			c = 0
		F[k] = c
		p += 1
	p = N
	cnt = 0
	p = N
	c = 0
	while p > 0:
		if s[p - 1] == '1':
			c += 1
		else:
			c = 0
		R[p] = c
		p -= 1
	mx = K
	for i in range(1, N + 2 - K):
		n = F[i - 1] + K + R[i + K]
		if n > mx:
			mx = n
	print(mx)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(input())
	l = [0] * (n + 2)
	r = [0] * (n + 2)
	result = 0
	for i in range(n):
		if a[i] == '1':
			l[i + 1] = l[i] + 1
	for i in range(n - 1, -1, -1):
		if a[i] == '1':
			r[i + 1] = r[i + 2] + 1
	i = 1
	while i + k - 1 <= n:
		result = max(result, l[i - 1] + k + r[i + k])
		i += 1
	print(result)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	m = k
	head = [0] * n
	tail = [0] * n
	head[0] = 0
	tail[-1] = 0
	for i in range(1, n):
		if s[i - 1] == '1':
			head[i] = 1 + head[i - 1]
	for i in range(n - 2, -1, -1):
		if s[i + 1] == '1':
			tail[i] = 1 + tail[i + 1]
	i = 0
	while i + k <= n:
		c = head[i] + k + tail[i + k - 1]
		m = max(m, c)
		i += 1
	print(m)


def solve():
	(n, k) = map(int, input().split())
	a = input()
	r = [0] * (n + 1)
	l = [0] * n
	for i in range(n):
		if a[i] == '1':
			l[i] = 1
			if i > 0:
				l[i] += l[i - 1]
		j = n - i - 1
		if a[j] == '1':
			r[j] = 1 + r[j + 1]
	mx = 0
	for i in range(n - k + 1):
		x = k + r[i + k]
		if i > 0:
			x += l[i - 1]
		if x > mx:
			mx = x
	print(mx)
t = 1
t = int(input())
for _test_ in range(t):
	solve()


for t in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(input())
	mxct = 0
	for i in range(n - k + 1):
		j = i - 1
		ct = k
		while j >= 0:
			if li[j] == '1':
				j -= 1
				ct += 1
			else:
				break
		j = i + k
		while j < n:
			if li[j] == '1':
				j += 1
				ct += 1
			else:
				break
		mxct = max(ct, mxct)
	print(mxct)


import numpy as np

def pizza_dagen(A, N, K):
	cons_before = [0] * (N - K + 1)
	curr = 0
	for i in range(N - K):
		if A[i] == '1':
			curr += 1
		else:
			curr = 0
		cons_before[i + 1] = curr
	cons_after = [0] * (N - K + 1)
	curr = 0
	for i in range(N - K - 1, -1, -1):
		if A[i + K] == '1':
			curr += 1
		else:
			curr = 0
		cons_after[i] = curr
	return min(N, K + np.max(np.array(cons_before) + np.array(cons_after)))

def main():
	T = int(input())
	for _ in range(T):
		(N, K) = [int(x) for x in input().split(' ')]
		A = input()
		print(pizza_dagen(A, N, K))
main()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = input()
	prefix = [0] * n
	suffix = [0] * n
	(i, j) = (0, 1)
	flag = arr[0] != '0'
	while i < n and j < n:
		if not flag and arr[j] == '1':
			i = j
			flag = True
		elif flag and arr[j] == '0':
			idx = 1
			while i < j:
				suffix[i] = j - i
				prefix[i] = idx
				idx += 1
				i += 1
			flag = False
		j += 1
	diff = j - i
	idx = 1
	while i < j and flag:
		prefix[i] = idx
		suffix[i] = j - i
		idx += 1
		i += 1
	max_len = k + suffix[k] if k < n else k
	for i in range(1, n - k):
		length = k + prefix[i - 1] + suffix[i + k]
		max_len = max(length, max_len)
	if n - k - 1 >= 0:
		max_len = max(prefix[n - k - 1] + k, max_len)
	print(max_len)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = input()
	head = [0 for i in range(N)]
	tail = [0 for i in range(N)]
	for i in range(1, N):
		if A[i - 1] == '1':
			head[i] = head[i - 1] + 1
	for i in range(N - 2, -1, -1):
		if A[i + 1] == '1':
			tail[i] = tail[i + 1] + 1
	res = 0
	for i in range(N - K + 1):
		res = max(res, head[i] + K + tail[i + K - 1])
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	left = [0] * n
	right = [0] * n
	if a[0] == '0':
		co = 0
	else:
		co = 1
	for i in range(1, n):
		left[i] = co
		if a[i] == '0':
			co = 0
		else:
			co += 1
	if a[n - 1] == 1:
		co = 1
	else:
		co = 0
	for i in range(n - 1, -1, -1):
		right[i] = co
		if a[i] == '0':
			co = 0
		else:
			co += 1
	if k == n:
		print(n)
	else:
		max = 1
		for i in range(0, n - k + 1):
			if max < left[i] + k + right[i + k - 1]:
				max = left[i] + k + right[i + k - 1]
		print(max)


def cob(l, n):
	i = n - 1
	count = 0
	while i != -1 and l[i] != 0:
		i -= 1
		count += 1
	return count

def coa(l, n, ll):
	i = n + 1
	count = 0
	while i != ll and l[i] != 0:
		i += 1
		count += 1
	return count
tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	l = list(map(int, list(input())))
	l1 = []
	for i in range(n - k + 1):
		l1.append(cob(l, i) + coa(l, i + k - 1, n))
	print(max(l1) + k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	head = [0] * n
	tail = [0] * n
	for i in range(1, n):
		if a[i - 1] == '1':
			head[i] = head[i - 1] + 1
		else:
			head[i] = 0
	for i in range(n - 2, -1, -1):
		if a[i + 1] == '1':
			tail[i] = tail[i + 1] + 1
		else:
			tail[i] = 0
	ans = 0
	i = 0
	while i + k <= n:
		ans = max(ans, k + head[i] + tail[i + k - 1])
		i += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	a = input()
	pre = [0] * n
	post = [0] * n
	count = 0
	for i in range(n):
		if a[i] == '1':
			count += 1
		else:
			count = 0
		pre[i] = count
	count = 0
	for i in range(n - 1, -1, -1):
		if a[i] == '1':
			count += 1
		else:
			count = 0
		post[i] = count
	sol = 0
	for i in range(0, n - k + 1):
		time = 0
		if i > 0:
			time += pre[i - 1]
		time += k
		if i + k < n:
			time += post[i + k]
		sol = max(sol, time)
	print(sol)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	ans = k
	s = input()
	l_before = [0 for i in range(n)]
	l_after = [0 for i in range(n)]
	for i in range(n):
		if s[i] == '1':
			l_before[i] = l_before[i - 1] + 1
	for j in range(-1, -n - 1, -1):
		if s[j] == '1':
			l_after[j] = l_after[j + 1] + 1
	for i in range(n - k + 1):
		if i >= 1 and i + k < n:
			ans = max(ans, k + l_before[i - 1] + l_after[i + k])
		elif i >= 1 and i + k >= n:
			ans = max(ans, k + l_before[i - 1])
		elif i < 1 and i + k < n:
			ans = max(ans, k + l_after[i + k])
		elif i < 1 and i + k >= n:
			ans = max(ans, k)
	print(ans)


def pizza_time(a, k, p, n):
	return (a.index('0', p + k) if '0' in a[p + k:] else n) - (a.rindex('0', 0, p) + 1 if '0' in a[:p] else 0)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()[:n]
	if not '0' in a:
		print(len(a))
		continue
	if not '1' in a:
		print(k)
		continue
	if len(a) == k:
		print(k)
		continue
	print(max([pizza_time(a, k, i, n) for i in range(n - k + 1)]))