import itertools

def kbits(n, k):
    result = []
    for bits in itertools.combinations(range(n), k):
        s = ['0'] * n
        for bit in bits:
            s[bit] = '1'
        result.append(''.join(s))
    return result

def g(s):
	mx = -1
	count = 1
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			count += 1
		else:
			count = 1
		mx = max(mx, count)
	return mx

def flip(s, k):
	s = list(s)
	for i in range(len(s)):
		if k[i] == "1":
			s[i] = '1' if s[i] == '0' else '0'
	return "".join(s)

def f(n, k, s):
	kbit = []
	for _k in range(k + 1):
		kbit.extend(kbits(n, _k))
	ans = 999999999999999999999
	for kb in kbit:
		ans = min(ans, g(flip(s, kb)))
	return ans


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