Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef is a well-known chef, and everyone wishes to taste his dishes.

As you might know, cooking is not an easy job at all and cooking everyday makes the chef very tired. So, Chef has decided to give himself some days off.

Chef has made a schedule for the next N days: On i-th day if A_{i} is equal to 1 then Chef is going to cook a delicious dish on that day, if A_{i} is equal to 0 then Chef is going to rest on that day.

After Chef made his schedule he discovered that it's not the best schedule, because there are some big blocks of consecutive days where Chef will cook which means it's still tiring for Chef, and some big blocks of consecutive days where Chef is going to rest which means chef will be bored doing nothing during these days.

Which is why Chef has decided to make changes to this schedule, but since he doesn't want to change it a lot, he will flip the status of at most K days. So for each day which Chef chooses, he will make it 1 if it was 0 or he will make it 0 if it was 1.

Help Chef by writing a program which flips the status of at most K days so that the size of the maximum consecutive block of days of the same status is minimized.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains two integers: N denoting the number of days and K denoting maximum number of days to change.

The second line contains a string of length N , of which the i-th character is 0 if chef is going to rest on that day, or 1 if chef is going to work on that day

------ Output ------ 

For each test case, output a single line containing a single integer, which is the minimum possible size of maximum block of consecutive days of the same status achievable.

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

1 ≤ T ≤ 11,000
1 ≤ N ≤ 10^{6}
The sum of N in all test-cases won't exceed 10^{6}.
0 ≤ K ≤ 10^{6}
0 ≤ A_{i} ≤ 1

------ Subtasks ------ 

Subtask #1 (20 points): N ≤ 10
Subtask #2 (80 points): Original Constraints 

----- Sample Input 1 ------ 
2
9 2
110001111
4 1
1001
----- Sample Output 1 ------ 
2
2
----- explanation 1 ------ 
Example case 1: The answer is 2 because we can change the string to: 110101011
Example case 2: If we don't change the input string at all, the answer will be 2. It is the best value we can achieve under the given conditions.

Difficulty: HARD
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
T = int(input())
while T:
	(N, K) = map(int, input().rstrip().rsplit())
	st = str(input())
	a = '01' * (N // 2)
	b = '10' * (N // 2)
	if N & 1:
		a += '0'
		b += '1'
	(n1, n2) = (0, 0)
	for i in range(N):
		if a[i] != st[i]:
			n1 += 1
		if b[i] != st[i]:
			n2 += 1
	if n1 <= K or n2 <= K:
		print(1)
	else:
		blocks = []
		count = 1
		for i in range(1, N):
			if st[i] != st[i - 1]:
				blocks.append(count)
				count = 1
			else:
				count += 1
		blocks.append(count)
		(l, r) = (2, N)
		while l < r:
			mid = (l + r) // 2
			c = 0
			for i in blocks:
				if i > mid:
					c += i // (mid + 1)
			if c > K:
				l = mid + 1
			else:
				r = mid
		print(l)
	T -= 1


def requiredLessThanK(m):
	count = 0
	for i in blocks:
		if i > m:
			count += i // (m + 1)
	return count <= k
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	cnt = 1
	blocks = []
	s1 = '01' * (n // 2)
	s2 = '10' * (n // 2)
	c1 = 0
	c2 = 0
	if n & 1:
		s1 += '0'
		s2 += '1'
	for i in range(n):
		if s1[i] == s[i]:
			c1 += 1
		if s2[i] == s[i]:
			c2 += 1
	if min(c1, c2) <= k:
		print(1)
	else:
		for i in range(1, n):
			if s[i] != s[i - 1]:
				blocks.append(cnt)
				cnt = 1
			else:
				cnt += 1
		blocks.append(cnt)
		l = 2
		r = n
		ans = n
		while l <= r:
			mid = (l + r) // 2
			if requiredLessThanK(mid):
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		print(ans)


def ispzbl(block, mid, k):
	c = 0
	for j in block:
		if j > mid:
			c += j // (mid + 1)
	return c <= k
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(input())
	block = []
	count = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			block.append(count)
			count = 1
		else:
			count += 1
	block.append(count)
	s1 = '10' * (n // 2)
	s2 = '01' * (n // 2)
	if n & 1:
		s1 += '1'
		s2 += '0'
	(cn1, cn2) = (0, 0)
	for i in range(n):
		if a[i] == s1[i]:
			cn1 += 1
		if a[i] == s2[i]:
			cn2 += 1
	if min(cn1, cn2) <= k:
		print(1)
	else:
		(low, high) = (2, n)
		ans = n
		while low <= high:
			mid = (low + high) // 2
			if ispzbl(block, mid, k):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		print(ans)


def possible(m):
	(left_contiguous_idx, right_contiguous_idx, flips) = (0, 0, 0)
	for i in range(n):
		if s[left_contiguous_idx] == s[right_contiguous_idx]:
			right_contiguous_idx += 1
		else:
			flips += (right_contiguous_idx - left_contiguous_idx) // (m + 1)
			left_contiguous_idx = right_contiguous_idx
			right_contiguous_idx += 1
	flips += (right_contiguous_idx - left_contiguous_idx) // (m + 1)
	return flips <= k
for _ in range(int(input().strip())):
	(n, k) = map(int, input().strip().split())
	s = [int(i) for i in input().strip()]
	s_copy_0 = s[:]
	s_copy_1 = s[:]
	s_copy_1[0] = 1 - s_copy_1[0]
	count_0 = 0
	count_1 = 1
	for i in range(1, n):
		if s_copy_0[i] == s_copy_0[i - 1]:
			s_copy_0[i] = 1 - s_copy_0[i - 1]
			count_0 += 1
		if s_copy_1[i] == s_copy_1[i - 1]:
			s_copy_1[i] = 1 - s_copy_1[i - 1]
			count_1 += 1
	if min(count_1, count_0) <= k:
		print(1)
	else:
		ans = n
		l = 2
		r = n
		while l < r:
			m = (l + r) // 2
			if possible(m):
				r = m
			else:
				l = m + 1
		print(r)


def solve(ls, l, k):
	for i in ls:
		p = len(i)
		if p > l:
			k -= p // (l + 1)
	if k < 0:
		return False
	return True
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = input()
	ls = list()
	prev = st[0]
	for i in st[1:]:
		if i != prev[-1]:
			ls.append(prev)
			prev = i
		else:
			prev += i
	ls.append(prev)
	s1 = '10' * (n // 2)
	s2 = '01' * (n // 2)
	if n % 2 != 0:
		s1 += '1'
		s2 += '0'
	a = b = 0
	for i in range(n):
		if s1[i] != st[i]:
			a += 1
		if s2[i] != st[i]:
			b += 1
	if min(a, b) <= k:
		print(1)
	else:
		(l, r, res) = (2, n, n)
		while l <= r:
			m = l + (r - l) // 2
			if solve(ls, m, k):
				res = min(res, m)
				r = m - 1
			else:
				l = m + 1
		print(res)


import math

def is_pzbl(grps, mid, m):
	req = 0
	for i in grps:
		if i <= mid:
			pass
		else:
			req += i // (mid + 1)
	return req <= m
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(input())
	grps = []
	i = 0
	c = 1
	while i < n - 1:
		if l[i] == l[i + 1]:
			c += 1
		else:
			grps.append(c)
			c = 1
		i += 1
	if c != 0:
		grps.append(c)
	s1 = ''
	s2 = ''
	for i in range(0, n):
		if i % 2 == 0:
			s1 += '0'
			s2 += '1'
		else:
			s1 += '1'
			s2 += '0'
	cnt1 = 0
	cnt2 = 0
	for i in range(0, n):
		if s1[i] != l[i]:
			cnt1 += 1
		if s2[i] != l[i]:
			cnt2 += 1
	r = min(cnt1, cnt2)
	if r <= m:
		print(1)
	else:
		low = 2
		high = n
		while low <= high:
			mid = (low + high) // 2
			if is_pzbl(grps, mid, m):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
		print(ans)


def fun(break_status, l, k):
	for i in break_status:
		p = len(i)
		if p > l:
			k -= p // (l + 1)
	if k < 0:
		return 0
	else:
		return 1
for _ in range(int(input().strip())):
	(n, k) = map(int, input().strip().split())
	chef_status = input()
	break_status = []
	prev = chef_status[0]
	for i in chef_status[1:]:
		if i != prev[-1]:
			break_status.append(prev)
			prev = i
		else:
			prev += i
	break_status.append(prev)
	s1 = '10' * (n // 2)
	s2 = '01' * (n // 2)
	if n % 2 != 0:
		s1 += '1'
		s2 += '0'
	a = 0
	b = 0
	for i in range(n):
		if s1[i] != chef_status[i]:
			a += 1
		if s2[i] != chef_status[i]:
			b += 1
	if min(a, b) <= k:
		print(1)
	else:
		start = 2
		ans = n
		end = n
		while start <= end:
			mid = (start + end) // 2
			if fun(break_status, mid, k):
				ans = min(ans, mid)
				end = mid - 1
			else:
				start = mid + 1
		print(ans)


def possible(z):
	l = 0
	r = 0
	tot = 0
	for i in range(n):
		if s[r] == s[l]:
			r += 1
		else:
			tot += (r - l) // (z + 1)
			l = r
			r += 1
	tot += (r - l) // (z + 1)
	return tot <= k
T = int(input())
while T > 0:
	(n, k) = map(int, input().split())
	s = list(map(int, list(input())))
	u = s[:]
	v = s[:]
	v[0] = 1 - v[0]
	c1 = 0
	c2 = 1
	for i in range(1, n):
		if u[i] == u[i - 1]:
			u[i] = 1 - u[i - 1]
			c1 += 1
		if v[i] == v[i - 1]:
			v[i] = 1 - v[i - 1]
			c2 += 1
	if min(c1, c2) <= k:
		res = 1
	else:
		lo = 2
		hi = n
		res = n
		while lo <= hi:
			mid = (lo + hi) // 2
			if possible(mid):
				res = min(mid, res)
				hi = mid - 1
			else:
				lo = mid + 1
	print(res)
	T -= 1


def transform():
	t1 = t2 = ''
	c1 = c2 = 0
	c = 1
	for i in range(n):
		t1 += str(c)
		t2 += str(1 - c)
		c = 1 - c
	for i in range(n):
		if t1[i] != s[i]:
			c1 += 1
		if t2[i] != s[i]:
			c2 += 1
	if k >= min(c1, c2):
		return 1
	blocks = []
	count = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			count += 1
		else:
			blocks.append(count)
			count = 1
	if count > 0:
		blocks.append(count)
	(low, high) = (1, n)
	while low < high:
		total = 0
		mid = (low + high) // 2
		for block_size in blocks:
			total += block_size // (mid + 1)
		if total > k:
			low = mid + 1
		else:
			high = mid
	if low == 1:
		low += 1
	return low
for tc in range(int(input())):
	(n, k) = map(int, input().strip().split(' '))
	s = input().strip()
	print(transform())


cases = int(input())
for _ in range(cases):
	(n, k) = list(map(int, input().split()))
	s = input().strip()

	def getans():
		s1 = s2 = ''
		cost1 = cost2 = 0
		c = 1
		for i in range(n):
			s1 += str(c)
			s2 += str(1 - c)
			c = 1 - c
		for i in range(n):
			if s[i] != s1[i]:
				cost1 += 1
			if s[i] != s2[i]:
				cost2 += 1
		if k >= min(cost1, cost2):
			return 1
		blocks = []
		c = 1
		for i in range(1, n):
			if s[i] == s[i - 1]:
				c += 1
			else:
				blocks.append(c)
				c = 1
		if c > 0:
			blocks.append(c)
		(lo, hi) = (1, n)
		while lo < hi:
			mid = (lo + hi) // 2
			cost = 0
			for i in blocks:
				cost += i // (mid + 1)
			if cost > k:
				lo = mid + 1
			else:
				hi = mid
		if lo == 1:
			lo += 1
		return lo
	print(getans())


def main():
	from sys import stdin, stdout
	t = int(stdin.readline())
	for i in range(t):
		(length, swaps) = map(int, stdin.readline().split())
		seq = list(stdin.readline())
		one = False
		temp = 0
		for j in range(length):
			if j % 2 == 0:
				if seq[j] != '1':
					temp += 1
			elif seq[j] != '0':
				temp += 1
			if temp > swaps:
				break
		if temp <= swaps:
			one = True
		else:
			temp = 0
			for j in range(length):
				if j % 2 == 0:
					if seq[j] != '0':
						temp += 1
				elif seq[j] != '1':
					temp += 1
				if temp > swaps:
					break
			if temp <= swaps:
				one = True
		if not one:
			blocks = []
			last = seq[0]
			counter = 1
			for k in seq[1:]:
				if k == last:
					counter += 1
				else:
					blocks.append(counter)
					counter = 1
					last = k
			blocks.append(counter)
			ll = 2
			ul = max(blocks)
			while ll <= ul:
				mid = ll + (ul - ll) // 2
				tempswaps = 0
				for a in blocks:
					tempswaps += a // (mid + 1)
				if tempswaps > swaps:
					ll = mid + 1
				elif tempswaps <= swaps:
					ul = mid - 1
			stdout.write(str(ll) + '\n')
		elif one:
			stdout.write(str(1) + '\n')
main()


t = int(input())
for i in range(t):
	(length, swaps) = map(int, input().split())
	seq = list(input())
	one = False
	temp = 0
	for j in range(length):
		if j % 2 == 0:
			if seq[j] != '1':
				temp += 1
		elif seq[j] != '0':
			temp += 1
		if temp > swaps:
			break
	if temp <= swaps:
		one = True
	else:
		temp = 0
		for j in range(length):
			if j % 2 == 0:
				if seq[j] != '0':
					temp += 1
			elif seq[j] != '1':
				temp += 1
			if temp > swaps:
				break
		if temp <= swaps:
			one = True
	if not one:
		blocks = []
		last = seq[0]
		counter = 1
		for k in seq[1:]:
			if k == last:
				counter += 1
			else:
				blocks.append(counter)
				counter = 1
				last = k
		blocks.append(counter)
		ll = 2
		ul = max(blocks)
		while ll <= ul:
			mid = ll + (ul - ll) // 2
			tempswaps = 0
			for a in blocks:
				tempswaps += a // (mid + 1)
			if tempswaps > swaps:
				ll = mid + 1
			elif tempswaps <= swaps:
				ul = mid - 1
		print(ll)
	elif one:
		print(1)


def solve(s, n, k):
	cnt1 = 0
	cnt2 = 0
	for i in range(n):
		if i % 2 == 0:
			if s[i] == '1':
				cnt1 += 1
			else:
				cnt2 += 1
		elif s[i] == '0':
			cnt1 += 1
		else:
			cnt2 += 1
	if k >= min(cnt1, cnt2):
		print(1)
		return
	blocks = []
	cnt = 1
	for (idx, bit) in enumerate(s):
		if idx == n - 1:
			break
		if idx < n - 1 and s[idx] != s[idx + 1]:
			blocks.append(cnt)
			cnt = 0
		cnt += 1
	blocks.append(cnt)
	low = 2
	high = n
	while low < high:
		L = int((low + high) / 2)
		flips = 0
		for x in blocks:
			flips += int(x / (L + 1))
		if flips <= k:
			high = L
		else:
			low = L + 1
	print(low)
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	s = input()
	solve(s, n, k)


def possible(a, mid, k):
	cnt = 0
	for i in a:
		cnt += i // (mid + 1)
	return cnt <= k
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	s = list(input())
	cur = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			a.append(cur)
			cur = 1
		else:
			cur += 1
	a.append(cur)
	k = min(k, n)
	c1 = 0
	c2 = 0
	for i in range(n):
		if int(s[i]) == 0:
			if i % 2 == 0:
				c1 += 1
			else:
				c2 += 1
		elif i % 2 == 1:
			c1 += 1
		else:
			c2 += 1
	if c1 <= k or c2 <= k:
		print(1)
		continue
	low = 2
	high = n
	ans = n
	while low <= high:
		mid = (low + high) // 2
		if possible(a, mid, k):
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	print(ans)


import heapq
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = input()
	ch = a[0]
	q = []
	len = 1
	lenc = []
	lg = 0
	for j in range(1, n):
		if a[j] == ch:
			len += 1
		else:
			if len > 1:
				lenc.append(len)
				lg += 1
			len = 1
			ch = a[j]
	if len > 1:
		lenc.append(len)
		lg += 1
	lenc.sort()
	s1 = ''
	s2 = ''
	for j in range(n):
		if j % 2 == 0:
			s1 += '0'
			s2 += '1'
		else:
			s1 += '1'
			s2 += '0'
	f1 = 0
	f2 = 0
	for j in range(n):
		if s1[j] == a[j]:
			f1 += 1
		if s2[j] == a[j]:
			f2 += 1
	an1 = min(f1, f2)
	if k >= an1:
		print(1)
		continue
	arr2 = []
	for j in range(lg):
		arr2.append(1)
		heapq.heappush(q, (-lenc[j], j))
	(m1, m2) = heapq.heappop(q)
	m1 = abs(m1)
	f1 = 1
	heapq.heappush(q, (-m1, m2))
	while 1:
		if m1 == 2 or f1 > k:
			break
		(lk1, lk2) = heapq.heappop(q)
		lk = arr2[lk2]
		n = (lenc[lk2] - lk) / (lk + 1)
		if n > (lenc[lk2] - lk) // (lk + 1):
			n += 1
		nn = int(n)
		heapq.heappush(q, (-nn, lk2))
		arr2[lk2] += 1
		(m1, m2) = heapq.heappop(q)
		m1 = abs(m1)
		heapq.heappush(q, (-m1, m2))
		f1 += 1
	print(m1)


from bisect import *
from math import ceil
for t in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = input()
	evens = [0, 0]
	odds = [0, 0]
	for i in range(0, n, 2):
		ai = int(a[i])
		evens[ai] += 1
	for i in range(1, n, 2):
		ai = int(a[i])
		odds[ai] += 1
	mink = min(evens[1] + odds[0], evens[0] + odds[1])
	if k >= mink:
		print(1)
		continue
	counts = [0]
	i = 0
	while i < n:
		try:
			j = a.index('1' if a[i] == '0' else '0', i + 1)
			counts.append(j - i)
			i = j
		except:
			counts.append(n - i)
			i = n
	counts.sort()
	splits = [(0, 0, 0)]
	for i in range(k):
		if counts[-1] >= splits[-1][0]:
			c = counts.pop()
			o = c
			ks = 0
		else:
			e = splits.pop()
			c = e[0]
			o = e[1]
			ks = e[2]
		if c == 2:
			print(2)
			break
		ks += 1
		e = (ceil((o - ks) / (ks + 1)), o, ks)
		insort(splits, e)
	else:
		print(max(counts[-1], splits[-1][0]))


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	k1 = k2 = 0
	for i in range(n):
		if int(s[i]) != i % 2:
			k1 += 1
		else:
			k2 += 1
	if k >= min(k1, k2):
		print(1)
		continue
	i = 0
	arr = []
	while i < n:
		arr.append(1)
		while i < n - 1 and s[i] == s[i + 1]:
			arr[-1] += 1
			i += 1
		i += 1
	t = 0
	ind = []
	for i in arr:
		if i == 2 or i == 1:
			ind.append(t)
		t += 1
	for i in ind[::-1]:
		arr.pop(i)
	for i in range(len(arr)):
		arr[i] = [arr[i], 1]
	while len(arr) != 0 and k != 0:
		arr.sort(key=lambda x: x[0] // x[1], reverse=True)
		curr = arr[0]
		if curr[0] // (curr[1] + 1) < 3:
			arr.pop(0)
		else:
			curr[1] += 1
		k -= 1
	if len(arr) == 0:
		print(2)
	else:
		maxi = -1
		for i in arr:
			maxi = max(maxi, i[0] // i[1])
		print(maxi)


def read_input():
	t = int(input())
	for _ in range(t):
		global n, l
		(n, k) = input().strip().split()
		(n, k) = (int(n), int(k))
		l = input().strip()
		lt = []
		p = 1
		for i in range(1, n):
			if l[i] == l[i - 1]:
				p += 1
			else:
				lt.append(p)
				p = 1
		lt.append(p)
		y1 = 0
		y2 = 0
		for i in range(len(l)):
			if i % 2 == 0:
				y1 += int(l[i]) ^ 0
				y2 += int(l[i]) ^ 1
			else:
				y1 += int(l[i]) ^ 1
				y2 += int(l[i]) ^ 0
		y = min(y1, y2)
		if y <= k:
			print(1)
		else:
			l = max(lt)
			start = 2
			end = max(lt)
			while start <= end:
				mid = (start + end) // 2
				z = k
				from math import ceil
				for x in lt:
					if x > mid:
						kct = 1
						while True:
							dskda = (x - kct) / (kct + 1)
							if ceil(dskda) <= mid:
								z -= kct
								break
							else:
								kct += 1
				if z >= 0:
					end = mid - 1
					l = mid
				else:
					start = mid + 1
			print(l)
read_input()


def reverse_insort(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	try:
		while lo < hi:
			mid = (lo + hi) // 2
			if x[0] > a[mid][0]:
				hi = mid
			elif x[0] < a[mid][0]:
				lo = mid + 1
			elif x[2] > a[mid][2]:
				hi = mid
			else:
				lo = mid + 1
	except:
		a.append(x)
		a.sort(key=lambda x: (x[0], x[2]), reverse=True)
		return
	a.insert(lo, x)

def get_counts(s, n):
	counts = []
	current_count = 0
	prev = None
	for i in range(n):
		if s[i] == prev:
			current_count += 1
		else:
			if current_count > 1:
				counts.append(current_count)
			current_count = 1
		prev = s[i]
	if current_count > 1:
		counts.append(current_count)
	counts.sort(reverse=True)
	return counts

def check_for_one(n, k, s):
	start_with_one = 0
	start_with_zero = 0
	for i in range(n):
		if i % 2 == int(s[i]):
			start_with_zero += 1
		else:
			start_with_one += 1
	return start_with_zero == 0 or start_with_one == 0 or min(start_with_zero, start_with_one) <= k
t = int(input().replace(' ', ''))
while t:
	t -= 1
	inputs = list(map(int, input().strip().split()))
	n = inputs[0]
	k = inputs[1]
	s = list(input().replace(' ', ''))
	if k >= n or check_for_one(n, k, s):
		print(1)
		continue
	counts = get_counts(s, n)
	op_counts = [{0: count, 1: 0, 2: count} for count in counts]
	if len(op_counts) == 1:
		print(max(2, op_counts[0][2] // (k + 1)))
		continue
	if op_counts[0][0] == 2 or k == 0:
		print(max(2, op_counts[0][0]))
		continue
	for i in range(k):
		if op_counts[0][0] == 2:
			break
		else:
			op_counts[0][1] += 1
			op_counts[0][0] = op_counts[0][2] // (op_counts[0][1] + 1)
		curr_e = op_counts[0]
		op_counts = op_counts[1:]
		reverse_insort(op_counts, curr_e)
	print(max(2, int(op_counts[0][0])))


def one(A):
	a = sum((A[i] != i % 2 for i in range(len(A))))
	b = sum((A[i] != 1 - i % 2 for i in range(len(A))))
	return min(a, b)

def calc(A, x):
	if x == 1:
		return one(A)
	flips = streak = 0
	A = [-1] + A + [-1]
	for i in range(1, len(A) - 1):
		if A[i] != A[i - 1]:
			streak = 1
		else:
			streak += 1
		if streak > x:
			A[i] = -1
			flips += 1
			streak = 1
	return flips
for t in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, list(input().strip())))
	lo = 1
	hi = n
	while lo < hi:
		mid = (lo + hi) // 2
		flips = calc(A[:], mid)
		if flips > k:
			lo = mid + 1
		else:
			hi = mid
	print(hi)


t = int(input())
for t0 in range(t):
	s = [int(i) for i in input().strip().split()]
	(n, k) = (s[0], s[1])
	a = input().strip()
	rc = []
	p = a[0]
	ct = 1
	reqd = 0
	m = 0
	for i in range(1, n):
		if a[i] == p:
			ct += 1
			if m == 0:
				reqd += 1
				m = 1
			else:
				m = 0
		else:
			rc.append(ct)
			ct = 1
			if m == 1:
				reqd += 1
			else:
				m = 0
			p = a[i]
	rc.append(ct)
	l = len(rc)
	fl = 2
	if reqd <= k or n - reqd <= k:
		print(1)
		continue
	l = len(rc)
	bol = [rc[i] for i in range(l)]
	bul = [0 for i in range(l)]
	mx = max(bol)
	if mx == 2:
		print(2)
		continue
	for i in range(k):
		ind = bol.index(mx)
		bul[ind] += 1
		noc = bul[ind] + 1
		bol[ind] = (rc[ind] - bul[ind]) // noc
		if (rc[ind] - bul[ind]) % noc != 0:
			bol[ind] += 1
		mx = max(bol)
		if mx == 2 or mx == 1:
			fl = 0
			break
	if fl == 0:
		print(2)
	else:
		print(int(mx))


def check(mid):
	count = 0
	for i in arr:
		count += i // (mid + 1)
	return count

def get(s, n, k):
	(low, high) = (2, n)
	while low < high:
		mid = (low + high) // 2
		if check(mid) <= k:
			high = mid
		else:
			low = mid + 1
	return low
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(f1, f0) = (1, 0)
	(tot1, tot0) = (0, 0)
	for i in range(n):
		if f1 != int(s[i]):
			tot0 += 1
		if f0 != int(s[i]):
			tot1 += 1
		(f0, f1) = (f0 ^ 1, f1 ^ 1)
	if min(tot0, tot1) <= k:
		print(1)
		continue
	(last, arr, count) = (s[0], [], 1)
	for i in range(1, n):
		if s[i] == last:
			count += 1
		else:
			last = s[i]
			arr.append(count)
			count = 1
	arr.append(count)
	print(get(s, n, k))


import math
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().strip().split()))
	s = input().strip()
	i = 0
	a = []
	(curr, prev, kk, flag) = ('0', '1', 0, 1)
	for i in range(0, n):
		if s[i] == curr:
			kk += 1
			if kk > k:
				flag = 0
				break
		(curr, prev) = (prev, curr)
	if flag == 1:
		print(1)
		continue
	(curr, prev, kk, flag) = ('1', '0', 0, 1)
	for i in range(0, n):
		if s[i] == curr:
			kk += 1
			if kk > k:
				flag = 0
				break
		(curr, prev) = (prev, curr)
	if flag == 1:
		print(1)
		continue
	i = 0
	while i < n:
		cur = s[i]
		start = i
		l = 0
		while i < n and s[i] == cur:
			i += 1
			l += 1
		a.append([l, l, 0])
	i = 0
	while i < k:
		a.sort(key=lambda r: r[1], reverse=True)
		if a[0][1] == 1:
			break
		a[0][2] += 1
		a[0][1] = math.ceil((a[0][0] - a[0][2]) / (a[0][2] + 1))
		i += 1
	a.sort(key=lambda r: r[1], reverse=True)
	if a[0][1] == 1:
		print(2)
	else:
		print(a[0][1])


def can(n, s, seg):
	ret = 0
	last = s[0]
	cnt = 0
	for i in range(n):
		if last != s[i]:
			cnt = 1
			last = s[i]
		else:
			cnt += 1
		if cnt > seg:
			last ^= 1
			if seg > 1 and i + 1 < n and (s[i + 1] == last):
				last ^= 1
			ret += 1
			cnt = 1
	ret2 = ret
	ret = 1
	last = s[0] ^ 1
	cnt = 1
	for i in range(1, n):
		if last != s[i]:
			cnt = 1
			last = s[i]
		else:
			cnt += 1
		if cnt > seg:
			last ^= 1
			if seg > 1 and i + 1 < n and (s[i + 1] == last):
				last ^= 1
			ret += 1
			cnt = 1
	return min(ret, ret2)

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = [int(c) for c in input().strip()]
		l = 1
		r = n
		while l < r:
			mid = (l + r) // 2
			if can(n, s, mid) <= k:
				r = mid
			else:
				l = mid + 1
		print(l)
main()


def is_valid(arr, k, lim):
	cnt = 0
	curr = arr[0]
	for x in arr:
		if x != curr:
			req = cnt // (lim + 1)
			if req > k:
				return False
			else:
				k -= req
				cnt = 0
			curr = x
		cnt += 1
	req = cnt // (lim + 1)
	if req > k:
		return False
	else:
		k -= req
	return True
for inp in range(int(input())):
	(N, K) = [int(x) for x in input().strip().split()]
	arr = input().strip()
	ans = N
	(low, high) = (2, N)
	while low <= high:
		mid = (low + high) // 2
		if is_valid(arr, K, mid):
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	if ans == 2:
		odd = arr[::2]
		even = arr[1::2]
		mink = min(odd.count('1') + even.count('0'), odd.count('0') + even.count('1'))
		if mink <= K:
			ans = 1
	print(ans)