Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

There are $N$ light bulbs in a row, numbered $1$ through $N$ from left to right. Each bulb can be in one of the states "on" or "off". Initially, all the bulbs are "off". Each bulb is also connected to its (at most two) adjacent bulbs by wires.

You should reach a state described by a given a binary string $S$ with length $N$ ― for each valid $i$, if the $i$-th character of $S$ is '1', the $i$-th bulb should be "on", and if it is '0', the $i$-th bulb should be "off". You may do that by performing the following steps in the given order:
1. Cut up to $K$ of the $N-1$ wires between adjacent bulbs (possibly none of them).
2. Switch on some bulbs (possibly none). Here, whenever two bulbs are still connected by wires (directly or indirectly) and one of them gets switched on, then the other one also gets switched on.
3. Disconnect some bulbs from the electrical network. Here, disconnecting a bulb switches it off, but it does not affect any other bulbs ― if a bulb was switched on before this step and it was not disconnected in this step, it remains switched on afterwards.

Minimise the number of bulbs you need to disconnect in step 3 in order to reach the given final state of the bulbs.

------  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 single string $S$.

------  Output ------
For each test case, print a single line containing one integer ― the smallest number of bulbs you need to disconnect.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$0 ≤ K < N ≤ 10^{5}$
$|S| = N$
$S$ contains only characters '0' and '1'
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

----- Sample Input 1 ------ 
1

5 2

01001
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 
Example case 1: We can cut the wires between pairs of bulbs $(2, 3)$ and $(4, 5)$, switch on bulbs $1$, $2$ and $5$, and then disconnect bulb $1$.

Source: codechef | Difficulty: HARD
Tags: Constructive algorithms

String algorithms

Greedy algorithms

Mathematics

Data structures

Ad-hoc


Solutions:
import heapq as hp

def solve(heap, k):
	li = heap.copy()
	s = 0
	while k >= 2 and len(li) > 0:
		s += hp.heappop(li)
		k -= 2
	return -s
for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	s = input()
	zeros = 0
	for ch in s:
		if ch == '0':
			zeros += 1
	if k < 1:
		print(zeros)
		continue
	l = 0
	while l < n and s[l] == '0':
		l += 1
	r = n - 1
	while r >= 0 and s[r] == '0':
		r -= 1
	if k < 2:
		print(zeros - max(l, n - r - 1))
		continue
	heap = []
	cnt = 0
	for i in range(l, r + 1):
		if s[i] == '0':
			cnt -= 1
		if s[i] == '1' and cnt < 0:
			hp.heappush(heap, cnt)
			cnt = 0
	x = solve(heap, k)
	y = solve(heap, k - 1)
	z = solve(heap, k - 2)
	ans = max(x, l + y, n - r - 1 + y, l + n - r - 1 + z)
	print(zeros - ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	st = en = cnt = 0
	l = []
	if s[0] == '0':
		st += 1
	if s[-1] == '0':
		en += 1
	for i in s:
		if i == '0':
			cnt += 1
		elif cnt > 0:
			l.append(cnt)
			cnt = 0
	if cnt > 0:
		l.append(cnt)
		cnt = 0
	n1 = len(l)
	if n1 == 0 or l[0] == n:
		print(0)
	elif n1 == 1:
		if st or en:
			if k >= 1:
				print(0)
			else:
				print(l[0])
		elif k >= 2:
			print(0)
		else:
			print(l[0])
	elif k % 2 == 0:
		if st and en:
			l[0] += l[-1]
			l.pop()
		l.sort()
		disconnetcs = 0
		for i in range(len(l) - k // 2):
			disconnetcs += l[i]
		print(disconnetcs)
	else:
		if st and en:
			if l[0] >= l[-1]:
				l = l[1:]
			else:
				l.pop()
		elif st:
			l = l[1:]
		elif en:
			l.pop()
		disconnetcs = 0
		l.sort()
		for i in range(len(l) - (k - 1) // 2):
			disconnetcs += l[i]
		print(disconnetcs)


def stipid(n, k, st):
	(mid, side, i, count) = ([], [], 0, 0)
	for i in range(len(st)):
		if st[i] == '1':
			break
	side.append(i)
	st = st[i:]
	for i in range(len(st) - 1, -1, -1):
		if st[i] == '1':
			break
	side.append(len(st) - 1 - i)
	st = st[0:i + 1]
	if len(st) == 0:
		print(0)
		return
	for i in range(len(st)):
		if st[i] == '0':
			count += 1
		elif count != 0:
			mid.append(count)
			count = 0
	(total, cuts) = (sum(mid + side), 0)
	mid.sort(reverse=True)
	side.sort(reverse=True)
	if k == 0:
		print(total)
		return
	if k & 1:
		k -= 1
		if len(side) > 0:
			cuts += side[0]
			del side[0]
	for i in range(len(mid)):
		if k > 2:
			cuts += mid[i]
			k -= 2
		else:
			break
	if k >= 2:
		if i < len(mid):
			cuts += max(sum(side), mid[i])
		else:
			cuts += sum(side)
	print(total - cuts)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = input()
	stipid(n, k, st)


for _ in range(int(input())):
	(z, cc, l1, f1, ans, a1, b1) = ([], 0, 0, 0, 0, 0, 0)
	(n, k) = map(int, input().split())
	s = list(input())
	for i in s:
		if i == '1':
			z.append(cc)
			cc = 0
		elif i == '0':
			cc += 1
	if cc > 0:
		z.append(cc)
	if s[n - 1] != '1':
		b1 = z[len(z) - 1]
	else:
		b1 = -1
	if s[0] == '1':
		a1 = -1
	else:
		a1 = z[0]
	z.sort(reverse=True)
	for i in range(len(z)):
		if k <= 1:
			ans += z[i]
		elif z[i] == b1 and l1 == 0:
			k -= 1
			l1 += 1
		elif z[i] == a1 and f1 == 0:
			k -= 1
			f1 += 1
		elif k >= 2:
			k -= 2
	(x1, y1) = (ans, ans)
	if k == 1:
		if l1 == 0 and b1 != -1:
			y1 = ans - b1
		if f1 == 0 and a1 != -1:
			x1 = ans - a1
	print(min(x1, y1))


t = int(input())
while t:
	t = t - 1
	(n, k) = map(int, input().split())
	s = input()
	start = 0
	for x in s:
		if x == '1':
			break
		start += 1
	end = 0
	for x in s[::-1]:
		if x == '1':
			break
		end += 1
	zero = 0
	a = []
	for x in s:
		if x == '1':
			if zero != 0:
				a.append(zero)
			zero = 0
		else:
			zero += 1
	a.append(zero)
	a = sorted(a, reverse=True)
	for i in range(len(a)):
		if k >= 1 and a[i] != 0:
			if a[i] == start and start != 0:
				start = 0
				k -= 1
				a[i] = 0
			elif a[i] == end and end != 0:
				k -= 1
				a[i] = 0
				end = 0
			elif k > 1:
				a[i] = 0
				k -= 2
	dis = 0
	for x in a:
		dis += x
	print(dis)


t = int(input())
for i in range(0, t):
	(a, b) = map(int, input().split())
	str1 = input()
	l1 = []
	ct = 0
	for j in range(0, a):
		if str1[j] == '0':
			ct += 1
		if str1[j] == '1' or j == a - 1:
			l1.append(ct)
			ct = 0
	if str1[-1] == '1':
		l1.append(0)
	if b == 1:
		yy = max(l1[0], l1[-1])
		z = sum(l1)
		ans = z - yy
	elif b == 0:
		z = sum(l1)
		ans = z
	else:
		length = len(l1)
		if b % 2 == 0:
			xx = l1[0] + l1[-1]
			arr2 = l1[1:length - 1]
			arr2.append(xx)
			arr2.sort(reverse=True)
			torem = int(b / 2)
			arr3 = arr2[torem:]
			ans = sum(arr3)
		else:
			xx = min(l1[0], l1[-1])
			arr2 = l1[1:length - 1]
			arr2.sort(reverse=True)
			torem = int(b / 2)
			arr3 = arr2[torem:]
			ans = sum(arr3) + xx
			xx = l1[0] + l1[-1]
			arr2 = l1[1:length - 1]
			arr2.append(xx)
			arr2.sort(reverse=True)
			torem = int(b / 2)
			arr3 = arr2[torem:]
			ans1 = sum(arr3)
			ans = min(ans, ans1)
	print(ans)


import heapq
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	arr = list(s)
	size = 0
	conn = 0
	cnt = []
	for i in range(len(s)):
		if s[i] == '0':
			size += 1
		else:
			if size != 0:
				cnt.append([-size, 2])
			size = 0
	if size != 0:
		cnt.append([-size, 2])
	if len(s) == 1:
		if s[0] == '0':
			cnt[0][1] = 1
	else:
		if s[0] == '0':
			cnt[0][1] = 1
		if s[-1] == '0':
			cnt[-1][1] = 1
	cnt.sort()
	vis = [False for i in range(len(cnt))]
	for i in range(len(cnt)):
		if k >= cnt[i][1]:
			k -= cnt[i][1]
			vis[i] = True
	ans = 0
	for i in range(len(cnt)):
		if vis[i] == False:
			ans -= cnt[i][0]
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	s1 = ['1'] * n
	loc = [[], []]
	diff = []
	(c0, c1) = [0, 0]
	t = 0
	if n > 1 and k != 0 and (s != ['0'] * n) and (s != ['1'] * n):
		for i in range(n):
			if s[i] == '0':
				loc[0].append(i)
				c0 += 1
			else:
				loc[1].append(i)
				c1 += 1
				i1 = c1 - 1
				if c1 > 1:
					diff.append([loc[1][i1 - 1], loc[1][i1] - loc[1][i1 - 1] - 1])
				elif c1 == 1:
					diff.append([-1, loc[1][i1]])
					t += diff[-1][1]
		diff.append([-2, n - loc[1][-1] - 1])
		t += diff[-1][1]
		diff = sorted(diff, key=lambda x: x[1], reverse=True)
		(i, l) = (0, len(diff))
		flag = 2
		while k > 0 and i < l:
			d = diff[i]
			if t > d[1] and k == 2 and (flag == 2):
				c0 -= t
				flag = 0
				k -= 2
			elif d[0] in [-1, -2] and flag > 0:
				k -= 1
				if d[0] == -1:
					s1[:d[1]] = ['0'] * d[1]
				else:
					s1[n - d[1]:n] = ['0'] * d[1]
				c0 -= d[1]
				flag -= 1
			elif k > 1:
				k -= 2
				s1[d[0] + 1:d[0] + d[1] + 1] = ['0'] * d[1]
				c0 -= d[1]
			i += 1
	elif s == ['0'] * n or s == ['1'] * n:
		c0 = 0
	else:
		c0 = s.count('0')
	print(c0)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	state_str = input()
	sum_edges = 0
	sum_zeroes = 0
	count = [0, 0]
	zeroes_arr = [[0, 0]]
	ans = 0
	if n > 1:
		for i in range(0, n):
			if state_str[i] == '0' and i == 0:
				count[0] += 1
				count[1] = 1
			elif state_str[i] == '0' and i != 0 and (i != n - 1):
				count[0] += 1
			elif state_str[i] != '0' or (state_str[i] == '0' and i == n - 1):
				if state_str[i] == '0' and i == n - 1:
					count[0] += 1
					count[1] = 1
				zeroes_arr.append(count)
				count = [0, 0]
		zeroes_arr.sort()
		for i in range(0, len(zeroes_arr)):
			if zeroes_arr[i][1] == 1:
				sum_edges += zeroes_arr[i][0]
			sum_zeroes += zeroes_arr[i][0]
		j = len(zeroes_arr) - 1
		k_dup = k
		while k > 0 and j > 0:
			if zeroes_arr[j][1] == 1:
				k -= 1
				zeroes_arr[j][0] = 0
			elif zeroes_arr[j][1] != 1 and k >= 2:
				k -= 2
				zeroes_arr[j][0] = 0
			j -= 1
		for i in range(0, len(zeroes_arr)):
			ans += zeroes_arr[i][0]
		if sum_edges > sum_zeroes - sum_edges and k_dup == 2:
			print(sum_zeroes - sum_edges)
		elif sum_zeroes == n:
			print(0)
		else:
			print(ans)
	else:
		print(0)
	t -= 1


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input()
	if n == 1:
		print(0)
	else:
		l = []
		c = 0
		st = 0
		en = 0
		if s[0] == '0':
			st = 1
		if s[-1] == '0':
			en = 1
		for i in s:
			if i == '0':
				c += 1
			else:
				if c > 0:
					l.append(c)
				c = 0
		if c > 0:
			l.append(c)
		if len(l) == 0 or l[0] == n:
			print(0)
		elif len(l) == 1:
			if st == 1 or en == 1:
				if k >= 1:
					print(0)
				else:
					print(l[0])
			elif k >= 2:
				print(0)
			else:
				print(l[0])
		elif k % 2 == 0:
			if st == 1 and en == 1:
				l[0] = l[0] + l[-1]
				l.pop()
			l.sort()
			su = 0
			for i in range(len(l) - k // 2):
				su += l[i]
			print(su)
		else:
			if st == 1 and en == 1:
				if l[0] >= l[-1]:
					l = l[1:]
				else:
					l.pop()
			elif st == 1:
				del l[0]
			elif en == 1:
				l.pop()
			l.sort()
			su = 0
			for i in range(len(l) - (k - 1) // 2):
				su += l[i]
			print(su)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	sree = input()
	siri = []
	c = 0
	for i in range(n):
		if sree[i] == '1':
			siri.append(c)
			c = 0
		else:
			c += 1
	if c != 0:
		siri.append(c)
	if c == 0 and sree[-1] == '1':
		siri.append(0)
	(first, check1) = (siri[0], 1)
	(last, check2) = (siri[-1], 1)
	shanth_total_sum = sum(siri)
	siri = sorted(siri, reverse=True)
	honey_sum = 0
	for a in siri:
		if k <= 0:
			break
		elif a == first and check1 == 1:
			k -= 1
			check1 = 0
			honey_sum += a
		elif a == last and check2 == 1:
			k -= 1
			check2 = 0
			honey_sum += a
		elif k > 1:
			k -= 2
			honey_sum += a
	print(shanth_total_sum - honey_sum)


def solnext(st, k):
	if len(set(st)) == 1:
		return 0
	if k == 0:
		return st.count('0')
	mid = list(map(len, st.split('1')))
	side = [mid.pop(0), mid.pop(-1)]
	mid.sort(reverse=True)
	mid = mid[:mid.index(0)] if 0 in mid else mid
	tsum = sum(mid) + sum(side)
	if k % 2 == 1:
		tsum -= max(side)
		side = [min(side)]
		k -= 1
	i = 0
	for i in range(len(mid)):
		if k > 2:
			k -= 2
			tsum -= mid[i]
		else:
			break
	if k >= 2:
		if i < len(mid):
			tsum -= max(mid[i], sum(side))
		else:
			tsum -= sum(side)
	return tsum
for test in range(int(input())):
	(n, k) = map(int, input().split())
	st = input()
	print(solnext(st, k))


def sol(n, k, st):
	side = []
	zmid = []
	count = 0
	for i in range(n):
		if st[i] == '1':
			break
	if i != 0:
		side.append(i)
		st = st[i:]
	r = st[::-1]
	for i in range(len(r)):
		if r[i] == '1':
			break
	if i != 0:
		side.append(i)
		st = st[:len(r) - i]
	if len(st) == 0:
		print(0)
		return
	for i in range(len(st)):
		if st[i] == '0':
			count += 1
		else:
			if count != 0:
				zmid.append(count)
			count = 0
	total = sum(zmid) + sum(side)
	zmid.sort(reverse=True)
	side.sort(reverse=True)
	cnts = 0
	gcut = 0
	if k == 0:
		print(total)
		return
	if k % 2 != 0:
		k -= 1
		if len(side) != 0:
			gcut += side[0]
			cnts += 1
	for i in range(len(zmid)):
		if k > 2:
			gcut += zmid[i]
			k -= 2
		else:
			break
	if k >= 2:
		if i < len(zmid):
			gcut += max(sum(side[cnts:]), zmid[i])
		else:
			gcut += sum(side[cnts:])
	print(total - gcut)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	st = input()
	sol(n, k, st)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count_0 = 0
	for i in s:
		if i == '0':
			count_0 += 1
	if count_0 == n or count_0 == 0:
		print(0)
		continue
	req1 = []
	req2 = []
	if s[0] == '0':
		x = 0
		for i in s:
			if i == '0':
				x += 1
			else:
				req1.append(x)
				break
	if s[-1] == '0':
		p = s[::-1]
		x = 0
		for i in p:
			if i == '0':
				x += 1
			else:
				req1.append(x)
				break
	z = 0
	b = 0
	flag = 0
	for i in range(n):
		if s[i] == '1' and flag == 0:
			z = i
			flag = 1
		elif s[i] == '1' and flag == 1:
			b = i
			if b - z > 1:
				req2.append(b - z - 1)
			z = i
		else:
			continue
	req1.sort()
	req2.sort()
	used = 0
	while k > 0:
		if k > 1:
			if len(req2) != 0 and len(req1) != 0:
				if req2[-1] > req1[-1]:
					used += req2.pop()
					k = k - 2
				else:
					used += req1.pop()
					k -= 1
			elif len(req2) != 0 and len(req1) == 0:
				used += req2.pop()
				k = k - 2
			elif len(req1) != 0 and len(req2) == 0:
				used += req1.pop()
				k = k - 1
		elif len(req1) != 0:
			used += req1.pop()
			k -= 1
		else:
			break
	print(count_0 - used)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(cut, beg, size) = ([], 0, 0)
	for i in range(n):
		if s[i] == '1':
			if size == 0:
				beg += 1
			else:
				if beg == 0:
					cut.append([-beg + i, 1])
				else:
					cut.append([-beg + i, 2])
				beg = i + 1
				size = 0
		else:
			size += 1
	if size != 0:
		cut.append([-beg + i + 1, 1])
	cut.sort(key=lambda i: (i[0], -i[1]), reverse=True)
	if cut:
		index = 0
		while k and index < len(cut):
			if k >= cut[index][1]:
				k -= cut[index][1]
				cut[index][0] = 0
			index += 1
		ans = 0
		for i in cut:
			ans += i[0]
		print(ans)
	else:
		print(0)


def cutter(Off, K):
	li = []
	dis = 0
	for i in range(0, len(Off)):
		li.append(Off[i][1])
	li.sort(reverse=True)
	i = 0
	for j in range(0, K, 2):
		li.remove(li[i])
	for i in range(0, len(li)):
		dis += li[i]
	print(dis)

def OffFinder(s, st):
	l = []
	i = 0
	li = -1
	N = len(s)
	if st == 'On':
		a = 1
		b = 0
	else:
		a = 0
		b = 1
	while i < N:
		if int(s[i]) == a:
			l.append([])
			li += 1
			l[li].append(i)
			for j in range(i + 1, N):
				if int(s[j]) == b:
					l[li].append(j - i)
					i = j + 1
					break
			else:
				l[li].append(N - i)
				i = N
		else:
			i += 1
	return l

def minDis(N, K, s):
	Off = OffFinder(s, 'Off')
	cutReqd = 0
	if int(s[0]) == 0:
		stoff = Off[0][1]
	if int(s[N - 1]) == 0:
		endoff = Off[len(Off) - 1][1]
	if int(s[0]) == 0:
		if int(s[N - 1]) == 0:
			cutReqd = (len(Off) - 2) * 2 + 2
		else:
			cutReqd = (len(Off) - 1) * 2 + 1
	elif int(s[N - 1]) == 0:
		cutReqd = (len(Off) - 1) * 2 + 1
	else:
		cutReqd = len(Off) * 2
	if cutReqd <= K:
		print(0)
	elif K % 2 != 0:
		if int(s[0]) == 0:
			if int(s[N - 1]) == 0:
				stoff = Off[0][1]
				endoff = Off[len(Off) - 1][1]
				if stoff > endoff:
					Off.remove(Off[0])
				else:
					Off.remove(Off[len(Off) - 1])
				cutter(Off, K - 1)
			else:
				Off.remove(Off[0])
				cutter(Off, K - 1)
		elif int(s[N - 1]) == 0:
			Off.remove(Off[len(Off) - 1])
			cutter(Off, K - 1)
		else:
			cutter(Off, K - 1)
	elif int(s[0]) == 0:
		if int(s[N - 1]) == 0:
			Off[0][1] += Off[len(Off) - 1][1]
			Off.remove(Off[len(Off) - 1])
			cutter(Off, K)
		else:
			cutter(Off, K)
	else:
		cutter(Off, K)
nT = int(input())
for i in range(0, nT):
	d = list(map(int, input().strip().split()))
	N = d[0]
	K = d[1]
	s = input().strip()
	minDis(N, K, s)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	center_bulbs = []
	side_bulbs = []
	s = input()
	fl = 0
	m = 0
	for j in range(n):
		if s[j] == '0':
			m += 1
			if not fl:
				if j == 0 or j == n - 1:
					fl = 2
				else:
					fl = 1
		elif m:
			if fl == 2:
				side_bulbs.append(m)
			else:
				center_bulbs.append(m)
			m = 0
			fl = 0
	if m:
		side_bulbs.append(m)
	side_bulbs.sort()
	center_bulbs.sort()
	x = k
	disconnections = 0
	(j, k) = (len(center_bulbs) - 1, len(side_bulbs) - 1)
	if j == -1 and k == 0:
		print(0)
	else:
		while j > -1 and k > -1 and (x > 0):
			if x > 3:
				j -= 1
				x -= 2
			elif x == 3:
				if center_bulbs[j] + side_bulbs[k] > sum(side_bulbs[0:k + 1]):
					k -= 1
					j -= 1
					x -= 3
				elif k == 0:
					k -= 1
					x -= 1
				else:
					k -= 2
					x -= 2
			elif x == 2:
				if sum(side_bulbs[0:k + 1]) > center_bulbs[j]:
					k -= 2
					x -= 2
				else:
					j -= 1
					x -= 2
			else:
				k -= 1
				x -= 1
		if j > -1:
			while j > -1 and x > 1:
				j -= 1
				x -= 2
			disconnections += sum(center_bulbs[0:j + 1])
		if k > -1:
			while k > -1 and x > 0:
				k -= 1
				x -= 1
			disconnections += sum(side_bulbs[0:k + 1])
		print(disconnections)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = 0
	side = list()
	mid = list()
	for c in s:
		if c == '0':
			l += 1
		else:
			break
	if l:
		side.append(l)
	s = s[l:]
	s = s[::-1]
	l = 0
	for c in s:
		if c == '0':
			l += 1
		else:
			break
	if l:
		side.append(l)
	s = s[l:]
	l = 0
	for c in s:
		if c == '0':
			l += 1
		elif l:
			mid.append(l)
			l = 0
	side.sort(reverse=True)
	mid.sort(reverse=True)
	total = sum(mid) + sum(side)
	cut = 0
	if k == 0:
		print(total)
	elif len(s) == 0:
		print(0)
	else:
		if k & 1:
			if len(side):
				cut += side[0]
				side.remove(side[0])
				k -= 1
		while k > 2:
			cut += mid[0]
			mid.remove(mid[0])
			k -= 2
		if k == 2:
			if len(mid):
				cut += max(mid[0], sum(side))
			else:
				cut += sum(side)
		print(total - cut)


test_cases = int(input())
for _ in range(test_cases):
	(n, k) = map(int, input().split())
	s = input()
	if s[0] == '0':
		flag = 0
	else:
		flag = 1
	count = 0
	l = []
	sl = [0, 0]
	for x in s:
		if flag == 0 and x == '0':
			count += 1
		elif flag == 0 and x == '1':
			l.append(count)
			count = 0
			flag = 1
		elif flag == 1 and x == '0':
			flag = 0
			count += 1
	if flag == 0:
		sl[1] = count
	if s[0] == '0' and len(l) > 0:
		sl[0] = l[0]
		l[0] = 0
	l.sort(reverse=True)
	sl.sort(reverse=True)
	length = len(l)
	if k == 0:
		i = 0
		sum = 0
		while i < len(l):
			sum += l[i]
			i += 1
		print(sum + sl[0] + sl[1])
	elif k == 1:
		i = 0
		sum = 0
		while i < len(l):
			sum += l[i]
			i += 1
		print(sum + sl[1])
	elif k % 2 == 0:
		i = (k - 1) // 2
		if i < len(l):
			if sl[0] + sl[1] < l[i]:
				l[i] = sl[0] + sl[1]
		sum = 0
		while i < len(l):
			sum += l[i]
			i += 1
		print(sum)
	else:
		i = (k - 2) // 2
		if i < len(l):
			if sl[0] + l[i] > sl[0] + sl[1]:
				l[i] = sl[1]
		sum = 0
		while i < len(l):
			sum += l[i]
			i += 1
		print(sum)


import math

def foo(s, k):
	arr = s.split('1')
	start = 0
	end = 0
	if len(arr) == 1:
		return 0
	start = len(arr[0])
	end = len(arr[-1])
	arr = list(map(len, arr[1:len(arr) - 1]))
	arr.sort(reverse=True)
	i = 0
	ans = start + end + sum(arr)
	while k > 3 and i < len(arr):
		ans -= arr[i]
		i += 1
		k -= 2
	if k == 1:
		ans -= max(start, end)
	elif k == 2 and i < len(arr):
		ans -= max(start + end, arr[i])
	elif k == 2:
		ans -= start + end
	elif k == 3 and i < len(arr):
		ans -= max(start + end, arr[i] + start, arr[i] + end)
	elif k == 3:
		ans -= start + end
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(foo(s, k))


def func(n, k, string):
	count = 0
	gcuts = 0
	sidecuts = 0
	total = 0
	zmid = []
	side = []
	for i in range(len(string)):
		if string[i] == '1':
			break
	if i != 0:
		side.append(i)
		string = string[i:]
	r = string[::-1]
	for i in range(len(r)):
		if r[i] == '1':
			break
	if i != 0:
		side.append(i)
		string = string[:len(r) - i]
	if len(string) == 0:
		print(0)
		return
	for i in range(len(string)):
		if string[i] == '0':
			count += 1
		else:
			if count != 0:
				zmid.append(count)
			count = 0
	total = sum(side) + sum(zmid)
	zmid = sorted(zmid, reverse=True)
	side = sorted(side, reverse=True)
	if k == 0:
		print(total)
		return
	if k % 2 != 0:
		k = k - 1
		if len(side) != 0:
			gcuts += side[0]
			sidecuts += 1
	for i in range(len(zmid)):
		if k > 2:
			gcuts += zmid[i]
			k = k - 2
		else:
			break
	if k >= 2:
		if i < len(zmid):
			gcuts += max(sum(side[sidecuts:]), zmid[i])
		else:
			gcuts += sum(side[sidecuts:])
	ans = total - gcuts
	print(ans)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	string = input()
	func(n, k, string)


ls = []
t = int(input())
for z in range(t):
	nk = list(map(int, input().rstrip().split()))
	n = nk[0]
	k = nk[1]
	b = input()
	bl = n
	ct0 = 0
	base0 = 0
	lst = []
	active = False
	side = []
	for i in range(bl):
		if b[i] == '1' and active == False:
			if base0 != 0:
				lst.append(ct0)
			else:
				side.append(ct0)
			active = True
			ct0 = 0
			base0 = i + 1
		elif b[i] == '0':
			active = False
			ct0 += 1
	if active == False:
		top = ct0
		side.append(top)
	lst.sort(reverse=True)
	side.sort(reverse=True)
	lsd = 0
	llst = 0
	while k > 0:
		kcurr = k
		if k % 2 == 1:
			k -= 1
			if side:
				lsd += 1
		elif lst:
			if lsd < len(side) and lst[llst] < sum(side[lsd:]):
				k -= len(side)
				side = []
			else:
				k -= 2
				llst += 1
		else:
			k = 0
			break
		if kcurr == k:
			k = 0
			break
	sm = 0
	sm = sum(lst[llst:]) + sum(side[lsd:])
	ls.append(sm)
for i in ls:
	print(i)


import sys
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().split('1')
	for i in range(len(s)):
		s[i] = len(s[i])
	out = 0
	if len(s) == 1:
		print(0)
	elif k % 2 == 0:
		s = s[1:-1] + [s[0] + s[-1]]
		s.sort(reverse=True)
		i = 0
		while k > 0 and i < len(s):
			k -= 2
			i += 1
		while i < len(s):
			out += s[i]
			i += 1
		print(out)
	else:
		on = [s[0], s[-1]]
		s = s[1:-1]
		s.sort(reverse=True)
		on.sort(reverse=True)
		f = sum(on)
		cov = False
		i = 0
		while k > 2 and i < len(s):
			if not cov:
				if s[i] + on[0] > f:
					k -= 2
					i += 1
				else:
					k -= 2
					cov = True
			else:
				i += 1
				k -= 2
		if not cov:
			out += on[1]
		while i < len(s):
			out += s[i]
			i += 1
		print(out)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(mid, side) = ([], [])
	(srt, end, i, ctr, add) = (0, n - 1, 0, 0, 0)
	if s.count('0') == n or s.count('1') == n:
		print(0)
	elif k == 0:
		print(s.count('0'))
	else:
		if s[0] == '0' or s[-1] == '0':
			while s[srt] == '0':
				srt += 1
			while s[end] == '0':
				i += 1
				end -= 1
			side.append(srt)
			side.append(i)
		for i in range(srt, end + 1):
			if s[i] == '0':
				ctr += 1
			else:
				mid.append(ctr)
				ctr = 0
		mid.sort(reverse=True)
		side.sort(reverse=True)
		if k % 2 != 0:
			k -= 1
			if len(side) != 0:
				add += side[0]
				side[0] = 0
		for i in range(len(mid)):
			if k > 2:
				add += mid[i]
				k -= 2
			else:
				break
		if k >= 2:
			if i < len(mid):
				add += max(sum(side), mid[i])
			else:
				add += sum(side)
		print(s.count('0') - add)


from sys import stdin, stdout
from math import gcd, log2, log10, floor, ceil
import math
from collections import defaultdict, OrderedDict
from bisect import bisect_left

def fun(n, k):
	s = list(input())
	l = [0]
	for i in range(n):
		if s[i] == '0':
			l[-1] += 1
		else:
			l.append(0)
	count1 = 0
	count2 = 0
	if s[0] == '0':
		count1 = l[0]
	if s[-1] == '0':
		count2 = l[-1]
	l.sort(reverse=True)
	indexa = 0
	while k > 0:
		if l[indexa] == count2 and k >= 1:
			k -= 1
			count2 = 0
			l[indexa] = 0
		elif l[indexa] == count1 and k >= 1:
			k -= 1
			count1 = 0
			l[indexa] = 0
		elif l[indexa] > 0 and k >= 2:
			l[indexa] = 0
			k -= 2
		indexa += 1
		if indexa == len(l):
			break
	return sum(l)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	answer = fun(n, k)
	print(answer)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	ans = 0
	st_0 = s.find('1')
	last_1 = s.rfind('1')
	end_0 = n - last_1 - 1
	d = {}
	tmp_cnt = 0
	for i in range(st_0, last_1 + 1):
		if s[i] == '0':
			tmp_cnt += 1
			d[tmp_cnt] = d.get(tmp_cnt, 0) + 1
			if tmp_cnt > 1:
				d[tmp_cnt - 1] -= 1
				if not d[tmp_cnt - 1]:
					del d[tmp_cnt - 1]
		else:
			tmp_cnt = 0
	a1 = max(st_0, end_0)
	a2 = min(st_0, end_0)
	if k % 2 == 1:
		k -= 1
		a1 = 0
	x = list(d.keys())
	x.append(a1 + a2)
	x.sort(reverse=True)
	d[a1 + a2] = d.get(a1 + a2, 0) + 1
	for (index, i) in enumerate(x):
		if k <= 1:
			break
		while d.get(i, 0) and k >= 2:
			k -= 2
			d[i] -= 1
	for (k, v) in d.items():
		ans += k * v
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(map(len, input().split('1')))
	sm = sum(s)
	l = s[0]
	r = s[len(s) - 1]
	fl = True
	fr = True
	s.sort(reverse=True)
	count = 0
	for i in s:
		if k <= 0:
			break
		if i == l and fl == True:
			k -= 1
			count += i
			fl = False
		elif i == r and fr == True:
			k -= 1
			count += i
			fr = False
		elif k > 1:
			k -= 2
			count += i
	print(sm - count)


for aww in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = s.split('1')
	b = []
	xx = []
	for w in range(len(a)):
		x = len(a[w])
		if x != 0:
			xx.append([-x, 2])
	if len(s) == 1:
		if s[0] == '0':
			xx[0][1] = 1
	else:
		if s[0] == '0':
			xx[0][1] = 1
		if s[-1] == '0':
			xx[-1][1] = 1
	xx.sort()
	d = 0
	vis = [False for i in range(len(xx))]
	for i in range(len(xx)):
		if k >= xx[i][1]:
			k -= xx[i][1]
			vis[i] = True
	for i in range(len(xx)):
		if vis[i] == False:
			d -= xx[i][0]
	print(d)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if '1' not in s:
		print('0')
	else:
		d = []
		p = ''
		for i in s:
			p += i
		first = p.index('1')
		p = p[::-1]
		last = p.index('1')
		last1 = n - last - 1
		count = 0
		for i in range(first, last1 + 1):
			if s[i] == '1' and count != 0:
				d.append(count)
				count = 0
			elif s[i] == '0':
				count += 1
			else:
				pass
		if k % 2 == 0:
			first = first + last
			d.append(first)
			d.sort(reverse=True)
			r = len(d)
			count1 = 0
			for i in range(len(d)):
				if k == 0:
					count1 = 1
					r = i
					break
				else:
					k -= 2
			if count1 == 1:
				count = 0
				for i in range(r, len(d)):
					count += d[i]
				print(count)
			else:
				print('0')
		else:
			count = 0
			d.sort(reverse=True)
			if k == 1:
				if first > last:
					count += last
				else:
					count += first
				for i in range(len(d)):
					count += d[i]
				print(count)
			else:
				k -= 3
				count1 = 0
				r = len(d)
				for i in range(len(d)):
					if k == 0:
						count1 = 1
						r = i
						break
					else:
						k -= 2
				if count1 == 1:
					count = 0
					if first > last:
						if last > d[r]:
							for i in range(r, len(d)):
								count += d[i]
						else:
							count += last
							for i in range(r + 1, len(d)):
								count += d[i]
					elif first > d[r]:
						for i in range(r, len(d)):
							count += d[i]
					else:
						count += first
						for i in range(r + 1, len(d)):
							count += d[i]
					print(count)
				else:
					print('0')


def solve(s, n, k):
	(l, r) = (0, n - 1)
	while l < n and s[l] == '0':
		l += 1
	while r > -1 and s[r] == '0':
		r -= 1
	(sides, mids) = ([l, n - 1 - r], [])
	cnt = 0
	for i in range(l, r + 1):
		if s[i] == '1':
			if cnt > 0:
				mids.append(cnt)
			cnt = 0
		else:
			cnt += 1
	res = 0
	mids.sort(reverse=True)
	zeros = sum(sides) + sum(mids)
	if k >= 2 * len(mids) + len(sides) or s == '0' * n:
		return 0
	if k % 2 == 1:
		zeros -= max(sides)
		sides = [min(sides)]
		k -= 1
	i = 0
	while k > 2:
		zeros -= mids[i]
		i += 1
		k -= 2
	if k == 1:
		zeros -= min(sides)
	elif k == 2:
		zeros -= max(mids[i], sum(sides))
	return zeros
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(solve(s, n, k))


for _ in range(int(input())):
	(n, kost) = map(int, input().split())
	a = list(input())
	val = []
	wt = []
	mybool = False
	count = 0
	for j in range(n):
		if a[j] == '1':
			break
	first = j
	if j == n - 1:
		print(0)
		continue
	for k in a[j:]:
		if k == '1':
			if mybool == False:
				mybool = True
				val.append(count)
			count = 0
		else:
			count += 1
			mybool = False
	if len(val) > 0:
		val.pop(0)
	last = count
	if kost % 2 == 0:
		val.append(first + last)
		val.sort(reverse=True)
		ans = sum(val[:kost // 2])
	else:
		val.sort(reverse=True)
		temp1 = sum(val[:(kost - 1) // 2]) + max(first, last)
		val.append(first + last)
		val.sort(reverse=True)
		temp2 = sum(val[:(kost - 1) // 2])
		ans = max(temp2, temp1)
	print(max(0, a.count('0') - ans))


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(len, input().split('1')))
	su = sum(s)
	count = 0
	l = s[0]
	r = s[len(s) - 1]
	lf = True
	rf = True
	s.sort(reverse=True)
	for i in s:
		if k <= 0:
			break
		if i == l and lf == True:
			count += i
			k -= 1
			lf = False
		elif i == r and rf == True:
			count += i
			k -= 1
			rf = False
		elif k > 1:
			k -= 2
			count += i
	print(su - count)


def func(n, k, string):
	total = string.count('0')
	if n == 0 or n == 1 or string.count('0') == 0 or (string.count('1') == 0):
		return 0
	first = string.index('1')
	last = string[::-1].index('1')
	lister = string[first:n - last].split('1')
	a1 = []
	if k == 1:
		return total - max(first, last)
	for e1 in lister:
		if len(e1) != 0:
			a1.append(len(e1))
	a1.sort(reverse=True)
	sumer = 0
	if 2 * len(a1) + 2 <= k:
		return 0
	elif k % 2 == 0:
		a1.append(first + last)
		a1.sort(reverse=True)
		p = int(k / 2)
		for e2 in a1[0:p]:
			sumer += e2
		return total - sumer
	else:
		p = k // 2 - 1
		for e3 in a1[0:p]:
			sumer += e3
		r1 = a1[p] + max(first, last)
		r2 = first + last
		sumer += max(r1, r2)
		return total - sumer
try:
	for i_itr in range(int(input())):
		(n, k) = map(int, input().split())
		string = input()
		output = func(n, k, string)
		print(output)
except:
	pass


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, k) = stdin.readline().split()
	lis = list(stdin.readline())
	if lis[-1] == '\n':
		lis.pop(-1)
	output_str = list(map(int, lis))
	n = int(n)
	k = int(k)
	flag1 = 0
	total = sum(output_str)
	if total == 0 or total == n:
		print('0')
		flag1 = 1
	elif k == 0:
		print(n - total)
		flag1 = 1
	if flag1 == 0:
		mid_zero = []
		end_zero = []
		flag = 0
		start_ind = -1
		end_ind = -1
		for (ind, val) in enumerate(output_str):
			if val == 0:
				if flag == 0:
					start_ind = ind
					flag = 1
			if val == 1:
				if flag == 1:
					end_ind = ind - 1
					if start_ind == 0:
						end_zero.append(end_ind - start_ind + 1)
					elif end_ind == n - 1:
						end_zero.append(end_ind - start_ind + 1)
					else:
						mid_zero.append(end_ind - start_ind + 1)
					flag = 0
		if flag == 1:
			end_zero.append(n - start_ind)
		mid_zero.sort(reverse=True)
		end_zero.sort(reverse=True)
		div = int(k / 2)
		rem = k % 2
		if rem == 1:
			if len(end_zero) > 0:
				end_zero.pop(0)
		len_mid = len(mid_zero)
		len_end = len(end_zero)
		for i in range(div):
			if len_mid > 0:
				if len_end > 0:
					len1 = mid_zero[0]
					len2 = end_zero[0]
					if len1 > len2:
						mid_zero.pop(0)
						len_mid -= 1
					else:
						end_zero.pop(0)
						len_end -= 1
						if len_end > 0:
							end_zero.pop(0)
							len_end -= 1
				else:
					mid_zero.pop(0)
					len_mid -= 1
		final = sum(mid_zero) + sum(end_zero)
		print(final)


try:
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		s = input()
		l = []
		j = 0
		t = k + 0
		while j < n:
			aj = -1
			if s[j] == '0':
				aj = j + 0
				cnt = 0
				while j < n and s[j] == '0':
					cnt += 1
					j += 1
				if aj == 0 or j == n:
					l.append([cnt, 1])
				else:
					l.append([cnt, 2])
			else:
				j += 1
		l.sort()
		l.reverse()
		v = len(l)
		j = 0
		while j < v and k - l[j][1] >= 0:
			k -= l[j][1]
			j += 1
		sm = 0
		while j < v:
			if k > 0 and l[j][1] == 1:
				k -= 1
			else:
				sm += l[j][0]
			j += 1
		l = []
		j = 0
		k = t + 0
		valu = 0
		while j < n:
			aj = -1
			if s[j] == '0':
				aj = j + 0
				cnt = 0
				while j < n and s[j] == '0':
					cnt += 1
					j += 1
				if aj == 0 or j == n:
					valu += cnt
				else:
					l.append([cnt, 2])
			else:
				j += 1
		l.append([valu, 2])
		l.sort()
		l.reverse()
		v = len(l)
		j = 0
		while j < v and k - l[j][1] >= 0:
			k -= l[j][1]
			j += 1
		tm = 0
		while j < v:
			if k > 0 and l[j][1] == 1:
				k -= 1
			else:
				tm += l[j][0]
			j += 1
		if len(set(list(s))) == 1:
			print(0)
		else:
			print(min(sm, tm))
except:
	pass


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l = []
	edge = []
	start = 0
	end = 0
	i = 0
	while i < len(s):
		count = 0
		while i < len(s) and s[i] == '0':
			count += 1
			i += 1
		if count:
			l.append(count)
		i += 1
	if s[0] == '0':
		if len(l):
			edge.append(l[0])
			l.pop(0)
	if s[n - 1] == '0':
		if len(l):
			edge.append(l[-1])
			l.pop()
	l.sort()
	edge.sort()
	if k == 1:
		if len(edge) == 1:
			edge.clear()
			k -= 1
		elif len(edge) == 2:
			edge.pop()
			k -= 1
	elif k % 2 == 0:
		while k > 0:
			if k > 2:
				if len(l):
					l.pop()
					k -= 2
				else:
					if len(edge):
						edge.clear()
					k = 0
			elif k == 2:
				if len(l) and len(edge):
					if sum(edge) >= l[-1]:
						edge.clear()
						k = 0
					else:
						l.pop()
						k = 0
				elif len(l) and (not len(edge)):
					l.pop()
					k = 0
				elif len(edge) and (not len(l)):
					edge.clear()
					k = 0
				else:
					k = 0
	else:
		while k > 0:
			if k > 3:
				if len(l):
					l.pop()
					k -= 2
				else:
					if len(edge):
						edge.clear()
					k = 0
			elif k == 3:
				if len(l) and len(edge):
					if sum(edge) >= edge[-1] + l[-1]:
						edge.clear()
						k = 0
					else:
						edge.pop()
						l.pop()
						k = 0
				elif len(l) and (not len(edge)):
					l.pop()
					k = 0
				elif len(edge) and (not len(l)):
					edge.clear()
					k = 0
				else:
					k = 0
	total = sum(l) + sum(edge)
	print(total)


import math

def solve(s, n, k):
	if k == 0:
		return s.count('0')
	else:
		i = 0
		m = k
		l = []
		e = []
		while i < n:
			if s[i] == '0':
				j = i + 1
				while j < n:
					if s[j] == '1':
						break
					j += 1
				if i == 0 or j == n:
					e.append(j - i)
				else:
					l.append(j - i)
				i = j
			i += 1
		l.sort(reverse=True)
		e.sort(reverse=True)
		mi = math.inf
		su = 0
		for i in l:
			k -= 2
			if k < 0:
				su += i
		mi = min(mi, su + sum(e))
		if e != []:
			su = 0
			k = m
			k -= 1
			for i in l:
				k -= 2
				if k < 0:
					su += i
			mi = min(mi, su + (0 if len(e) == 1 else e[-1]))
		if len(e) == 2:
			k = m
			if k >= 2:
				k -= 2
				su = 0
				for i in l:
					k -= 2
					if k < 0:
						su += i
				mi = min(mi, su)
		return mi
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	print(solve(s, n, k))


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split(' ')))
	s = input()
	count_0 = 0
	for i in s:
		if int(i) == 0:
			count_0 += 1
	if count_0 == n:
		print(0)
		continue
	one_cut = [0]
	two_cut = [0]
	cnt = 0
	for i in s:
		if int(i) == 1:
			break
		else:
			cnt += 1
	one_cut.append(cnt)
	cnt = 0
	for i in range(len(s) - 1, -1, -1):
		if int(s[i]) == 1:
			break
		else:
			cnt += 1
	one_cut.append(cnt)
	j = 0
	while j < n - 1:
		if int(s[j]) == 1:
			j += 1
			cnt = 0
			while j < n and int(s[j]) != 1:
				j += 1
				cnt += 1
			if j != n:
				two_cut.append(cnt)
		else:
			j += 1
	used = 0
	one_cut.sort()
	two_cut.sort()
	while k > 0:
		if two_cut[-1] > one_cut[-1] and k > 1:
			used += two_cut[-1]
			if len(two_cut) > 1:
				two_cut.pop()
			else:
				two_cut[-1] = 0
			k -= 2
		else:
			used += one_cut[-1]
			if len(one_cut) > 1:
				one_cut.pop()
			else:
				one_cut[-1] = 0
			k -= 1
	print(count_0 - used)


def solve_helper(s, k):
	if k < 0:
		return 1000000000000
	zerocounts = []
	tempcount = 0
	for i in s:
		if i == '0':
			tempcount += 1
		else:
			if tempcount > 0:
				zerocounts.append(tempcount)
			tempcount = 0
	zerocounts.sort()
	while k > 1 and len(zerocounts) > 0:
		zerocounts.pop()
		k -= 2
	ans = 0
	for item in zerocounts:
		ans += item
	return ans

def solve(s, k):
	begcount = 0
	endcount = 0
	s1 = ''
	flag = True
	for i in s:
		if flag and i == '0':
			begcount += 1
		else:
			flag = False
			s1 += i
	while s1[-1] == '0':
		endcount += 1
		s1 = s1[:-1]
	finalans = min(solve_helper(s1, k) + begcount + endcount, min(solve_helper(s1, k - 1) + begcount, min(solve_helper(s1, k - 1) + endcount, solve_helper(s1, k - 2))))
	return finalans

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input()
		count = 0
		for i in s:
			if i == '0':
				count += 1
		if count == 0 or count == n:
			print(0)
		else:
			print(solve(s, k))
main()


import collections
import math
import sys

def CountFrequency(arr):
	return collections.Counter(arr)
try:
	for case in range(int(input())):
		(n, k) = map(int, input().split())
		s = list(input())
		indx = []
		zero = []
		zc = 0
		for i in range(len(s)):
			if s[i] == '1':
				indx.append(i)
			else:
				zc += 1
		if len(indx) != 0:
			if indx[0] != 0:
				zero.append((indx[0], 1))
			if indx[-1] != n - 1:
				zero.append((n - 1 - indx[-1], 1))
			for i in range(len(indx) - 1):
				zero.append((indx[i + 1] - indx[i] - 1, 2))
			zero.sort(key=lambda x: x[0], reverse=True)
			for i in zero:
				if k >= 2:
					zc -= i[0]
					k -= i[1]
				elif k == 1 and i[1] == 1:
					zc -= i[0]
					k -= 1
				if k == 0:
					break
			print(zc)
		else:
			print(0)
except:
	pass


import collections
import math
import sys

def CountFrequency(arr):
	return collections.Counter(arr)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ls = list(input())
	(i, zero_cnt, sp_lst) = (0, 0, [])
	while i < len(ls):
		if ls[i] == '0':
			temp = i
			while i < len(ls) and ls[i] == '0':
				i += 1
			if temp == 0 or i == len(ls):
				sp_lst.append((i - temp, 1))
				zero_cnt += i - temp
			else:
				sp_lst.append((i - temp, 2))
				zero_cnt += i - temp
		i += 1
	sp_lst.sort(key=lambda e: (e[0], -e[1]), reverse=True)
	for e in sp_lst:
		if k >= 2:
			zero_cnt -= e[0]
			k -= e[1]
		elif k == 1 and e[1] == 1:
			zero_cnt -= e[0]
			k -= 1
		if k == 0:
			break
	print(zero_cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ls = list(input())
	(i, zero_cnt, sp_lst) = (0, 0, [])
	while i < len(ls):
		if ls[i] == '0':
			temp = i
			while i < len(ls) and ls[i] == '0':
				i += 1
			if temp == 0 or i == len(ls):
				sp_lst.append((i - temp, 1))
				zero_cnt += i - temp
			else:
				sp_lst.append((i - temp, 2))
				zero_cnt += i - temp
		i += 1
	sp_lst.sort(key=lambda e: (e[0], -e[1]), reverse=True)
	for e in sp_lst:
		if k >= 2:
			zero_cnt -= e[0]
			k -= e[1]
		elif k == 1 and e[1] == 1:
			zero_cnt -= e[0]
			k -= 1
		if k == 0:
			break
	print(zero_cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	bulbs = list(map(len, input().split('1')))
	total = sum(bulbs)
	cuts = 0
	lside = bulbs[0]
	rside = bulbs[-1]
	sidel = True
	sider = True
	bulbs.sort(reverse=True)
	for i in bulbs:
		if k <= 0:
			break
		elif i == lside and sidel == True:
			k -= 1
			cuts += i
			sidel = False
		elif i == rside and sider == True:
			k -= 1
			cuts += i
			sider = False
		elif k > 1:
			k -= 2
			cuts += i
	print(total - cuts)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	if n == 1:
		print([1, 0][n])
	elif k == 0:
		print(n - s.count('1'))
	else:
		p1 = 0
		p2 = n - 1
		pz = 0
		sz = 0
		if s[0] == '0':
			for i in range(n):
				p1 = i
				if s[i] != '0':
					break
				pz += 1
		if s[-1] == '0':
			for i in range(n - 1, p1, -1):
				p2 = i
				if s[p2] != '0':
					break
				sz += 1
		z = 0
		arr = []
		for i in range(p1 + 1, p2 + 1):
			if s[i] != '0':
				if s[i - 1] == '0':
					arr.append(z)
				z = 0
			else:
				z += 1
		arr = sorted([pz, sz]) + sorted(arr)
		if len(arr) <= 2:
			if k >= 2:
				print(0)
			elif k == 1:
				print(min(arr))
		else:
			ptr = len(arr) - 1
			ans = sum(arr)
			while k > 3 and ptr >= 0:
				ans -= arr[ptr]
				k -= 2
				ptr -= 1
			if ptr != -1:
				if ptr >= 2:
					if k == 1:
						ans -= max(arr[:2])
					elif k == 2:
						ans -= max(arr[1] + arr[0], arr[ptr])
					else:
						ans -= max(arr[1] + arr[0], max(arr[:2]) + arr[ptr])
				elif ptr == 1:
					if k == 1:
						ans -= max(arr[0], arr[1])
					else:
						ans -= arr[0] + arr[1]
				elif ptr == 0:
					if k >= 1:
						ans -= arr[0]
			print(ans)


try:
	T = int(input())
	while T:
		(N, K) = tuple(map(int, input().split()))
		S = input()
		ls = list(S)
		temp = []
		part = 0
		countz = 0
		lflag = 0
		final = []
		lz = 0
		rz = 0
		for x in ls:
			if x == '0':
				countz += 1
				if lflag == 0:
					lz += 1
			if x == '1':
				part += 1
				lflag = 1
			if part == 1:
				if x == '0':
					temp.append(x)
			if part == 2:
				if len(temp) > 0:
					final.append(len(temp))
				temp = []
				part = 1
		if part == 1 and len(temp) > 0:
			rz = len(temp)
		final.sort(reverse=True)
		if K % 2 != 0 and K > 0:
			countz = countz - max(lz, rz)
			K = K - 1
			if K > 0:
				maincutsec = K // 2
				if len(final) >= maincutsec:
					if maincutsec == 1 and min(rz, lz) > final[0]:
						countz = countz - min(rz, lz)
					elif maincutsec == 1:
						countz -= final[0]
					if maincutsec > 1:
						countz = countz - sum(final[:maincutsec - 1])
						if min(lz, rz) > final[maincutsec - 1]:
							countz = countz - min(lz, rz)
						else:
							countz = countz - final[maincutsec - 1]
				else:
					countz = countz - sum(final) - min(lz, rz)
		else:
			maincutsec = K // 2
			if len(final) >= maincutsec:
				if maincutsec == 1 and rz + lz > final[0]:
					countz = countz - (rz + lz)
				elif maincutsec == 1:
					countz -= final[0]
				if maincutsec > 1:
					countz = countz - sum(final[:maincutsec - 1])
					if rz + lz > final[maincutsec - 1]:
						countz = countz - (rz + lz)
					else:
						countz = countz - final[maincutsec - 1]
			else:
				countz = countz - sum(final) - (rz + lz)
		print(countz)
		T = T - 1
except:
	pass


from sys import stdin, stdout, setrecursionlimit
import heapq
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007
tc = ii1()
for _ in range(tc):
	(n, k) = iia()
	s = is1()
	if set(s) == set(['0']):
		print(0)
		continue
	(one, two) = ([], [])
	start = end = None
	for i in range(n):
		if s[i] == '0':
			if start == None:
				start = i
				end = i
			else:
				end = i
		elif start != None:
			if start == 0:
				one.append(end - start + 1)
			else:
				two.append(end - start + 1)
			start = end = None
	if start != None:
		one.append(n - start)
	one = deque(sorted(one, reverse=True))
	two = deque(sorted(two, reverse=True))
	while k > 0:
		if len(one) and len(two) and (one[0] >= two[0]):
			one.popleft()
			k -= 1
		elif len(two) and k > 1:
			two.popleft()
			k -= 2
		else:
			while k > 0 and len(one):
				k -= 1
				one.popleft()
			break
	print(sum(one) + sum(two))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if k == 0:
		print(s.count('0'))
		continue
	if s.count('0') == n:
		print(0)
		continue
	if k == 0:
		print(s.count('0'))
		continue
	front = 0
	back = 0
	while s[front] == '0':
		front += 1
	i = n - 1
	while s[i] == '0':
		i -= 1
		back += 1
	cons = []
	zero = 0
	flag = 0
	for i in range(front, n - back):
		if s[i] == '0':
			flag = 1
			zero += 1
		if s[i] == '1':
			if flag:
				cons.append(zero)
				zero = 0
				flag = 0
	cons.sort()
	cons.reverse()
	if cons == []:
		if k == 1:
			print(min(front, back))
			continue
		if k == 0:
			print(front + back)
			continue
		elif k > 1:
			print(0)
			continue
	if k % 2:
		if front > back:
			front = 0
		else:
			back = 0
		k -= 1
	if front + back > cons[0]:
		front = 0
		back = 0
		k -= 2
	i = 0
	while cons[i] >= front + back and k > 0:
		cons[i] = 0
		k -= 2
		i += 1
		if i > len(cons) - 1:
			break
	if k:
		front = 0
		back = 0
		k -= 2
	while k > 0 and i < len(cons):
		cons[i] = 0
		k -= 2
		i += 1
	print(sum(cons) + front + back)


pi = int(input())
for t in range(0, pi):
	(a, b) = map(int, input().split())
	piii = input()
	count_1 = 0
	for i in piii:
		if i == '1':
			count_1 += 1
	split = []
	part = []
	for i in range(0, a):
		part.append(piii[i])
		if i + 1 < a:
			if piii[i] != piii[i + 1]:
				split.append(part)
				part = []
		else:
			split.append(part)
	if len(split) - 1 <= b:
		print(0)
	else:
		count = []
		count_0 = []
		bg = 0
		eg = 0
		for i in range(0, len(split)):
			count.append([int(split[i][0]), len(split[i])])
		for i in range(0, len(split)):
			if count[i][0] == 0:
				count_0.append(len(split[i]))
		count_0.sort(reverse=True)
		for i in count_0:
			if b >= 1:
				if count[len(split) - 1] == [0, i] and eg < 1:
					a = a - i
					b = b - 1
					eg = 1
				elif count[0] == [0, i] and bg < 1:
					a = a - i
					b = b - 1
					bg = 1
				elif b >= 2:
					a = a - i
					b = b - 2
		print(a - count_1)


import sys
import math
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	s = input()
	start = 0
	end = 0
	mid = []
	i = 0
	while i < n and s[i] == '0':
		start += 1
		i += 1
	if i == n:
		print(0)
	else:
		j = n - 1
		while j >= 0 and s[j] == '0':
			end += 1
			j -= 1
		count = 0
		i += 1
		while i < j:
			if s[i] == '0':
				count += 1
			elif count > 0:
				mid.append(count)
				count = 0
			i += 1
		if count > 0:
			mid.append(count)
		mid.sort(reverse=True)

		def solve(k, mid):
			size = len(mid)
			ans = 999999999
			if k >= 0:
				ans = sum(mid[min(k // 2, size):])
			return ans
		a1 = solve(k, mid) + start + end
		a2 = solve(k - 1, mid) + min(start, end)
		a3 = solve(k - 2, mid)
		print(min(a1, a2, a3))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ns = s
	arr = ns.split('1')
	arr = [len(x) for x in arr if x]
	weird = []
	if len(arr) >= 2:
		if s[0] == '0':
			weird.append(arr[0])
		if s[-1] == '0':
			weird.append(arr[-1])
	elif len(arr) == 1:
		if s[0] == '0':
			weird.append(arr[0])
		elif s[-1] == '0':
			weird.append(arr[0])
	arr = list(sorted(arr, reverse=True))
	i = 0
	len_arr = len(arr)
	while i < len_arr and k:
		t = arr[i]
		if t in weird:
			if t == weird[0]:
				weird.pop(0)
			else:
				weird.pop()
			arr[i] = 0
			k -= 1
		elif k >= 2:
			arr[i] = 0
			k -= 2
		i += 1
	print(sum(arr))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = []
	t = 0
	for i in range(n):
		if s[i] == '0':
			t += 1
		else:
			if len(d) == 0:
				d.append([t, 1])
			else:
				d.append([t, 2])
			t = 0
	f = 0
	if t != 0:
		if len(d) == 0:
			f = 1
		d.append([t, 1])
	d.sort(key=lambda x: x[1])
	d.sort(reverse=True, key=lambda x: x[0])
	if f == 1:
		print(0)
	else:
		for i in d:
			if k >= i[1]:
				k -= i[1]
				i[0] = 0
		out = 0
		for i in d:
			out += i[0]
		print(out)


def shukla(store, n, cuts, st):
	c = 0
	val = st.count('0')
	for i in range(n):
		if st[i] == '0':
			c += 1
			i += 1
		else:
			break
	xv = c
	i = n - 1
	c = 0
	while i < n:
		if st[i] == '0':
			c += 1
			i -= 1
		else:
			break
	yv = c
	c = 0
	for i in range(xv, n - yv):
		if st[i] == '0':
			c += 1
		elif c:
			store.append(c)
			c = 0
	if c:
		store.append(c)
	if cuts == 2:
		if len(store) > 0:
			val -= max(xv + yv, max(store))
			print(val)
		else:
			val -= xv + yv
			print(val)
		return
	store.sort(reverse=True)
	if cuts % 2 == 1:
		val -= max(xv, yv)
		cuts -= 1
		i = 0
		while cuts > 0:
			if i > len(store) - 1:
				if cuts > 0:
					if min(xv, yv) > 0:
						val = 0
				break
			if store[i] > min(xv, yv):
				val -= store[i]
				i += 1
				cuts -= 2
			else:
				val -= min(xv, yv)
				cuts -= 2
				xv = -1
				yv = -1
		print(val)
	else:
		i = 0
		while cuts > 0:
			if i > len(store) - 1:
				if cuts > 0:
					if cuts == 1 and (xv > 0 or yv > 0):
						val -= max(xv, yv)
					else:
						if xv > 0:
							val -= xv
						if yv > 0:
							val -= yv
				break
			if store[i] > xv + yv:
				val -= store[i]
				i += 1
				cuts -= 2
			else:
				val -= xv + yv
				cuts -= 2
				xv = -1
				yv = -1
		print(val)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	store = []
	val = s.count('0')
	if k == 0:
		print(val)
	elif val == n or val == 0:
		print(0)
	else:
		shukla(store, n, k, s)


for i in range(int(input())):
	(inp, size) = map(int, input().split())
	battlepass = input()
	valorant = list(map(int, list(battlepass)))
	sage = list(map(len, battlepass.split('1')))
	breach = True
	brim = True
	for i in range(sage.count(0)):
		sage.remove(0)
	cnt = 0
	raze = sorted(sage, reverse=True)
	jett = list(sage)
	for i in range(len(raze)):
		if cnt < size:
			if sage[0] == raze[i] and valorant[0] == 0 and breach:
				cnt += 1
				breach = False
				jett.remove(raze[i])
			elif sage[-1] == raze[i] and valorant[-1] == 0 and brim:
				cnt += 1
				brim = False
				jett.remove(raze[i])
			elif cnt + 1 < size:
				cnt += 2
				jett.remove(raze[i])
	print(sum(jett))


for a0 in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	l = [x for x in input().strip()]
	(s1, s2, cut) = (0, 0, 0)
	s = []
	r = []
	if l[0] == '0' and n > 1 and (l[1] != l[0]):
		s1 += 1
		s2 += 1
	if l[-1] == '0' and n > 1 and (l[-2] != l[-1]):
		s1 += 1
	tp = l[0]
	c = -1
	for i in range(len(l)):
		c += 1
		if l[i] != tp:
			if tp == '1':
				c = 0
			elif l[0] == '0' and s == []:
				s.append(c)
			else:
				r.append(c)
			cut += 1
			tp = l[i]
			if i < n - 1 and l[i] == '0' and (l[i] != l[i + 1]):
				s2 += 1
			if i == n - 1 and l[i] == '0':
				s2 += 1
	if tp == '0':
		s.append(c + 1)
	r.sort(reverse=True)
	if s != [] and s[0] < s[-1]:
		(s[0], s[-1]) = (s[-1], s[0])
	if cut <= k:
		print(0)
	else:
		if k % 2 == 1 and s != []:
			cut -= 1
			k -= 1
			del s[0]
		if s == []:
			for i in range(k // 2):
				del r[0]
			print(sum(r))
		else:
			while True:
				if (k == 1 or k == 0) or s == []:
					break
				if r[0] > s[0]:
					k -= 2
					cut -= 2
					del r[0]
				else:
					cut -= 1
					k -= 1
					del s[0]
			while True:
				if k == 0 or k == 1:
					break
				del r[0]
				k -= 2
				cut -= 2
			if k == 1 and len(s) > 0:
				del s[0]
			print(sum(r) + sum(s))


for T in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	bulbs = s.split('1')
	c = [len(i) for i in bulbs if i != '']
	if c == []:
		print('0')
	else:
		(f_c, l_c) = (0, 0)
		(first, last) = (False, False)
		if s[0] == '0':
			f_c = c[0]
			first = True
		if s[-1] == '0':
			l_c = c[-1]
			last = True
		(f, l) = (0, 0)
		c.sort()
		b = False
		for i in range(len(c) - 1, -1, -1):
			if k <= 2:
				b = True
				break
			if c[i] == f_c and (not f):
				k -= 1
				f = 1
			elif c[i] == l_c and (not l):
				k -= 1
				l = 1
			else:
				k -= 2
		if i == 0 and b == False:
			print('0')
		else:
			i += 1
			val = 0
			for j in range(i):
				val += c[j]
			if k == 2:
				if last == True and first == True:
					if l == 0 and f == 0:
						val -= max(l_c + f_c, c[i - 1])
					else:
						val -= c[i - 1]
				else:
					val -= c[i - 1]
			elif k == 1:
				if last == True and first == True:
					if l == 0 and f == 0:
						val -= max(l_c, f_c)
					elif l == 1 and f == 0:
						val -= f_c
					elif l == 0 and f == 1:
						val -= l_c
				elif last == True and first == False:
					if l == 0:
						val -= l_c
				elif last == False and first == True:
					if f == 0:
						val -= f_c
			print(val)


for _ in range(int(input())):
	(n, k) = (int(x) for x in input().split())
	s = input()
	if len(s) == 1:
		print(0)
	else:
		ind = 0
		cnt = 0
		ini = 0
		sth = 0
		last = 0
		flag = 1
		data = []
		while ind < len(s):
			if s[ind] == '1' and sth == 0:
				if ini == 0 and ind != 0:
					ini += ind
				elif ini == 0 and ind == 0:
					flag = 0
				if cnt == 0:
					cnt = 1
			elif s[ind] == '0' and cnt == 1:
				sth += 1
				if ind == len(s) - 1:
					last += sth
			elif s[ind] == '1' and sth != 0:
				cnt = 0
				data.append(sth)
				sth = 0
				if ind != len(s) - 1 and s[ind + 1] == '0':
					cnt = 1
			ind += 1
		ind = len(data) - 1
		if k > 1:
			data.sort()
		if flag == 0:
			ini = 0
		ini_ = ini
		last_ = last
		data_ = data[:]
		k_ = k
		while k != 0:
			if k % 2 != 0:
				if ini > last:
					ini = 0
				else:
					last = 0
				k -= 1
			while ind >= 0 and k > 0:
				ind -= 1
				k -= 2
			if ind == -1 and k > 0:
				if k > 1:
					ini = 0
					last = 0
				elif ini > last:
					ini = 0
				else:
					last = 0
			break
		ans = ini + last
		if ind >= 0:
			ans += sum(data[:ind + 1])
		ini = ini_
		last = last_
		k = k_
		data = data_[:]
		ind = len(data) - 1
		while k > 0:
			if k % 2 != 0:
				if ini > last:
					ini = 0
				else:
					last = 0
				k -= 1
			else:
				while k > 2 and ind >= 0:
					ind -= 1
					k -= 2
				if ini != 0 and last != 0 and (ind >= 0) and (ini + last > data[ind]):
					ini = 0
					last = 0
					k -= 2
				elif ini != 0 and last != 0 and (ind >= 0):
					ind -= 1
					k -= 2
				elif ini != 0 and last != 0:
					ini = 0
					last = 0
					k -= 2
					break
				else:
					if ini > last:
						ini = 0
					else:
						last = 0
					break
		ans_ = ini + last
		if ind >= 0:
			ans_ += sum(data[:ind + 1])
		print(min(ans, ans_))


import heapq

def printNumber(N, K, string):
	k = 1
	if string[0] == '1':
		k = 2
	heap = []
	zeros = 0
	total_zeros = 0
	for val in string:
		if val == '1':
			heapq.heappush(heap, (-1 * zeros, k))
			total_zeros += zeros
			zeros = 0
			k = 2
		else:
			zeros += 1
	if zeros != 0:
		heapq.heappush(heap, (-1 * zeros, 1))
		total_zeros += zeros
	while heap != [] and K > 0:
		item = heapq.heappop(heap)
		if K >= item[1]:
			total_zeros -= item[0] * -1
			K -= item[1]
	print(total_zeros)
try:
	T = int(input())
except:
	exit()
for t in range(T):
	line = input().split()
	string = list(input())
	printNumber(int(line[0]), int(line[1]), string)


t = int(input())
for _ in range(t):
	l = []
	(n, k) = map(int, input().split())
	s = input()
	temp = 0
	flag = 0
	for i in range(n):
		if s[i] == '1':
			flag = 1
			l.append(temp)
			temp = 0
		else:
			temp += 1
	if flag == 0:
		print(0)
	else:
		l.append(temp)
		m = l[1:len(l) - 1]
		m.sort()
		m.reverse()
		a1 = sum(l)
		if k > 0:
			a1 -= max(l[0], l[-1])
			k1 = k - 1
			k1 = k1 // 2
			for i in range(min(k1, len(m))):
				a1 -= m[i]
		a2 = sum(l)
		k1 = k // 2
		for i in range(min(k1, len(m))):
			a2 -= m[i]
		a3 = sum(l)
		if k > 1:
			a3 -= l[0]
			a3 -= l[-1]
			k1 = k - 2
			k1 = k1 // 2
			for i in range(min(k1, len(m))):
				a3 -= m[i]
		print(min(a1, a2, a3))


for _ in range(int(input())):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	s = input()
	a = []
	if s.count('1') == 0:
		print(0)
	else:
		hello = -1
		for i in range(n):
			if s[i] == '1':
				if hello == -1:
					a.append(i - hello - 1)
				elif i - hello - 1 > 0:
					a.append(i - hello - 1)
				hello = i
		interst1 = a[0]
		interst2 = n - 1 - hello
		a.remove(a[0])
		a.sort(reverse=True)
		j = -1
		ax = 0
		while k > 2:
			j += 1
			k -= 2
		if j > len(a) - 1:
			print(0)
		else:
			if k == 0:
				ax += interst1 + interst2
			elif k == 2:
				if j == len(a) - 1:
					ax = 0
				elif max(a[j + 1], interst1 + interst2) == a[j + 1] or (interst1 == 0 and interst2 == 0):
					j += 1
					ax += interst1 + interst2
			elif j == -1 and min(a[0], interst1, interst2) == a[0]:
				ax = min(interst1, interst2)
			elif min(a[j], interst1, interst2) == a[j]:
				ax = a[j]
			else:
				ax += min(interst1, interst2)
			ax += sum(a[j + 1:])
			print(ax)


T = int(input())
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	output = [int(x) for x in input()]
	bulbs = [0 for i in range(N)]
	zeros_and_req_cut = []
	req_cut = 1
	zero_count = 0
	one_count = 0
	for o in range(len(output)):
		if output[o] == 0:
			zero_count += 1
		else:
			one_count += 1
			if zero_count != 0:
				zeros_and_req_cut.append((zero_count, req_cut))
			req_cut = 2
			zero_count = 0
	if zero_count != 0:
		zeros_and_req_cut.insert(0, (zero_count, 1))
	zeros_and_req_cut.sort(key=lambda x: x[0], reverse=True)
	turn_off = 0
	for z in range(len(zeros_and_req_cut)):
		(zeros, cuts) = zeros_and_req_cut[z]
		if K >= cuts:
			K -= cuts
		else:
			turn_off += zeros
	if one_count == 0:
		print(0)
	else:
		print(turn_off)