You are given a binary string $s$ of length $n$.

Let's define $d_i$ as the number whose decimal representation is $s_i s_{i+1}$ (possibly, with a leading zero). We define $f(s)$ to be the sum of all the valid $d_i$. In other words, $f(s) = \sum\limits_{i=1}^{n-1} d_i$.

For example, for the string $s = 1011$:

$d_1 = 10$ (ten);

$d_2 = 01$ (one)

$d_3 = 11$ (eleven);

$f(s) = 10 + 01 + 11 = 22$.

In one operation you can swap any two adjacent elements of the string. Find the minimum value of $f(s)$ that can be achieved if at most $k$ operations are allowed.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.

First line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $0 \le k \le 10^9$) — the length of the string and the maximum number of operations allowed.

The second line of each test case contains the binary string $s$ of length $n$, consisting of only zeros and ones.

It is also given that sum of $n$ over all the test cases doesn't exceed $10^5$.


-----Output-----

For each test case, print the minimum value of $f(s)$ you can obtain with at most $k$ operations.


-----Examples-----

Input
3
4 0
1010
7 1
0010100
5 2
00110
Output
21
22
12


-----Note-----

For the first example, you can't do any operation so the optimal string is $s$ itself. $f(s) = f(1010) = 10 + 01 + 10 = 21$.

For the second example, one of the optimal strings you can obtain is "0011000". The string has an $f$ value of $22$.

For the third example, one of the optimal strings you can obtain is "00011". The string has an $f$ value of $12$.

Difficulty: MEDIUM
Tags: Constructive algorithms

String algorithms

Greedy algorithms

Complete search

Mathematics
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
from sys import stdin

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

def read_int():
	return int(input())

def read_ints():
	return map(int, input().split())
t = read_int()
for case_num in range(t):
	(n, k) = read_ints()
	s = input()
	m = s.count('1')
	if m == 0:
		print(0)
	elif m == n:
		print(11 * (n - 1))
	else:
		ans = 11 * m
		l = s.find('1')
		r = s.rfind('1')
		lneed = l
		rneed = n - 1 - r
		if k >= lneed + rneed and m > 1:
			ans = 11 * (m - 1)
		elif k >= rneed:
			ans = 11 * m - 10
		elif k >= lneed:
			ans = 11 * m - 1
		print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count1 = 0
	for i in range(n):
		if s[i] == '1':
			count1 += 1
			r = i
			if count1 == 1:
				l = i
	if not count1:
		print(0)
		continue
	ans = count1 * 11
	r = n - r - 1
	if k >= r:
		ans -= 10
		count1 -= 1
		k -= r
	if k >= l and count1:
		ans -= 1
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	s = input().strip()
	cnt = 0
	f = n + 1
	b = -1
	for i in range(n):
		if s[i] == '1':
			cnt += 1
			f = min(f, i)
			b = max(b, i)
	if cnt == 0:
		return 0
	(op1, op2) = (f, n - 1 - b)
	if f == b:
		if op2 <= k:
			return 1
		elif op1 <= k:
			return 10
		else:
			return 11
	ans = 11 * cnt
	if op2 <= k:
		ans -= 10
		k -= op2
	if op1 <= k:
		ans -= 1
		k -= op1
	return ans
for _ in range(int(input())):
	print(solve())


from cmath import sqrt
from collections import defaultdict
from math import *
import sys
from typing import Counter
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = list(map(str, input().split()))[0]
	b = s.find('1')
	e = n - s.rfind('1') - 1
	c = s.count('1')
	ans = c * 11
	if e <= k:
		ans -= 10
		k -= e
		if c != 1 and b <= k:
			ans -= 1
	elif b <= k:
		ans -= 1
	if c:
		print(ans)
	else:
		print(0)


x = int(input())
ret = []
for z in range(x):
	(n, k) = input().split()
	k = int(k)
	a = input()
	spl = False
	lst = a.split('1')
	(l, r, x) = (0, 0, 0)
	l = len(lst[0])
	r = len(lst[-1])
	ones = len(lst) - 1
	min = ones * 11
	if l == len(a):
		ret.append(min)
		continue
	if k >= l + r:
		x = 11
		spl = True
	elif k >= r:
		x = 10
	elif k >= l:
		x = 1
	if ones == 1 and spl:
		x = 10
	min = min - x
	ret.append(min)
for i in ret:
	print(i)


t = int(input())
ans = list()
for i in range(0, t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input()]
	arr_sum = 0
	j = n - 1
	if k >= n:
		d = 0
	else:
		d = n - k - 1
	while j >= d:
		if arr[j] == 1:
			arr[j] = 0
			arr_sum += 1
			k -= n - 1 - j
			break
		j -= 1
	else:
		arr_sum += arr[-1]
	for j in range(0, min([k + 1, n])):
		if arr[j] == 1:
			arr[j] = 0
			arr_sum += 10
			break
	else:
		arr_sum += 10 * arr[0]
	for i in range(1, n - 1):
		arr_sum += 11 * arr[i]
	ans.append(arr_sum)
for s in ans:
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	if '1' in a:
		can = 1
		ans = a.count('1') * 11
		if a[::-1].index('1') <= k:
			k -= a[::-1].index('1')
			ans -= 10
			if a.count('1') == 1:
				can = 0
		if a.index('1') <= k and can:
			ans -= 1
		print(ans)
	else:
		print(0)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	p = s.count('1')
	if p == 0:
		print(0)
		continue
	l = s.find('1')
	f = n - s.rfind('1') - 1
	if p == 1:
		if f < k + 1:
			print(1)
		elif l < k + 1:
			print(10)
		else:
			print(11)
	elif l + f < k + 1:
		print(11 * p - 11)
	elif f < k + 1:
		print(11 * p - 10)
	elif l < k + 1:
		print(11 * p - 1)
	else:
		print(11 * p)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	for i in s[::-1]:
		if i == '0':
			count += 1
		else:
			break
	count_end = count
	count = 0
	for i in s:
		if i == '0':
			count += 1
		else:
			break
	count_start = count
	if s.count('1') == 0:
		print(0)
	elif s.count('1') == 1:
		if count_end <= k:
			print(1)
		elif count_start <= k:
			print(10)
		else:
			print(11)
	elif count_end <= k and count_end + count_start <= k:
		print((s.count('1') - 1) * 11)
	elif count_end <= k:
		print((s.count('1') - 1) * 11 + 1)
	elif count_start <= k:
		print((s.count('1') - 1) * 11 + 10)
	else:
		print(s.count('1') * 11)


I = input
for _ in [0] * int(I()):
	(n, k) = map(int, I().split())
	s = I()
	(i, j) = (x.find('1') % 8 ** 10 for x in (s, s[::-1]))
	print(11 * s.count('1') - (i <= k and (k >= i + j < n - 1 or j > k)) - 10 * (j <= k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	one = 0
	b = n
	e = 0
	for i in range(n):
		if s[i] == '1':
			one += 1
			if b == n:
				b = i
			e = i
	offset = 0
	if one > 0 and n - 1 - e <= k:
		one -= 1
		offset += 1
		k -= n - 1 - e
	if one > 0 and b <= k:
		one -= 1
		offset += 10
	print(11 * one + offset)


def evaluateStr():
	(n, swaps) = map(int, input().split())
	s = str(input())
	closest_front = closest_back = dist_front = dist_back = -1
	ones_count = 0
	flag = False
	for i in range(n):
		if s[i] == '1':
			ones_count += 1
			closest_back = i
			if not flag:
				closest_front = i
				flag = True
	dist_front = closest_front
	dist_back = n - 1 - closest_back
	if closest_front == -1:
		return 0
	elif ones_count == 1:
		if dist_back <= swaps:
			return 1
		elif dist_front <= swaps:
			return 10
		else:
			return 11
	elif dist_front + dist_back <= swaps:
		return (ones_count - 2) * 11 + 10 + 1
	elif dist_back <= swaps:
		return (ones_count - 1) * 11 + 1
	elif dist_front <= swaps:
		return (ones_count - 1) * 11 + 10
	else:
		return ones_count * 11
n = int(input())
for i in range(n):
	print(evaluateStr())


i = input()
for a in range(0, int(i)):
	[n, k] = [int(x) for x in input().split()]
	s = input()
	num = s.count('1')
	score = num * 11
	if num == 0:
		print(0)
	elif num == 1:
		p = s.index('1')
		if n - 1 - p <= k:
			print(1)
		elif p <= k:
			print(10)
		else:
			print(11)
	else:
		pl = s.index('1')
		pr = s[::-1].index('1')
		if pr <= k:
			score -= 10
			k -= pr
		if pl <= k:
			score -= 1
		print(score)


t = int(input())
for c in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	s = input()
	(first, last) = (-1, -1)
	sum = 0
	for i in range(n):
		if s[i] == '1':
			sum += 11
			if first < 0:
				first = i
			last = i
	if sum:
		lswp = n - last - 1
		if first != last and first + lswp <= k:
			sum -= 11
		elif lswp <= k:
			sum -= 10
		elif first <= k:
			sum -= 1
	print(sum)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c1 = s.count('1')
	if c1 == 0:
		print(0)
		continue
	(fo, lo) = (s.find('1'), s[::-1].find('1'))
	ans = c1 * 11
	if c1 > 1:
		if k >= lo:
			ans -= 10
			k -= lo
		if k >= fo:
			ans -= 1
	elif k >= lo:
		ans -= 10
	elif k >= fo:
		ans -= 1
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	num = s.count('1')
	tot = 0
	if num == 1:
		i = s.index('1')
		j = n - s.rfind('1') - 1
		if k >= j:
			k -= j
			tot += 1
			num -= 1
		elif k >= i:
			k -= i
			tot += 10
			num -= 1
		tot += num * 11
		print(tot)
	elif num > 1:
		i = s.index('1')
		j = n - s.rfind('1') - 1
		if k >= j:
			k -= j
			tot += 1
			num -= 1
		if k >= i:
			k -= i
			tot += 10
			num -= 1
		tot += num * 11
		print(tot)
	else:
		print(0)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	b = s.find('1')
	e = n - s.rfind('1') - 1
	c = s.count('1')
	ans = c * 11
	if e <= k:
		ans -= 10
		k -= e
		if c != 1 and b <= k:
			ans -= 1
	elif b <= k:
		ans -= 1
	if c:
		print(ans)
	else:
		print(0)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = input()
	c = list(c)
	if c.count('1'):
		y = c.index('1')
		s = c.count('1') * 11
		c = c[::-1]
		x = c.index('1')
		if x <= b:
			b = b - x
			s -= 10
			if y <= b and c.count('1') != 1:
				s -= 1
		elif y <= b:
			s -= 1
		print(s)
	else:
		print(0)


t = int(input())
for _ in range(t):
	(n, o) = map(int, input().split())
	s = input()
	res = 0
	if s.count('1'):
		min_pos = s.index('1')
		res = s.count('1') * 11
		s = s[::-1]
		max_pos = s.index('1')
		if max_pos <= o:
			o -= max_pos
			res -= 10
			if s.count('1') != 1 and min_pos <= o:
				res -= 1
		elif min_pos <= o:
			res -= 1
		print(res)
	else:
		print(0)


def solve():
	(n, k) = map(int, input().split())
	s = input()
	mone = s.count('1')
	ls = s.find('1')
	rs = n - s.rfind('1') - 1
	ans = mone * 11
	if rs <= k:
		ans -= 10
		k -= rs
		if mone != 1 and ls <= k:
			ans -= 1
	elif ls <= k:
		ans -= 1
	if mone:
		print(ans)
	else:
		print(0)
for t in range(int(input())):
	solve()


T = int(input())
q = []
for i in range(T):
	a = input().split()
	(n, k) = (int(a[0]), int(a[1]))
	ins = input()
	data = []
	for i in ins:
		data.append(i)
	q.append((n, k, data))

def solve(n, k, data):
	first_one = -1
	last_one = -1
	for (idx, c) in enumerate(data):
		if c == '1':
			if first_one == -1:
				first_one = idx
			if last_one < idx:
				last_one = idx
	if first_one != -1 and k >= n - last_one - 1:
		temp = data[n - 1]
		data[n - 1] = data[last_one]
		data[last_one] = temp
		k -= n - last_one - 1
		if first_one == last_one:
			last_one = -1
	if last_one != -1 and k >= first_one:
		temp = data[0]
		data[0] = data[first_one]
		data[first_one] = temp
	sol = 0
	for i in range(n - 1):
		sol += int(data[i] + data[i + 1])
	print(sol)
for (n, k, data) in q:
	solve(n, k, data)


t = int(input())

def solve(t):
	(n, k) = map(int, input().split())
	s = input()
	(first, last) = (10 ** 10, -10 ** 10)
	num = s.count('1')
	sum_ = num * 11
	for i in range(n):
		if s[i] == '1':
			first = i + 1
			break
	for i in range(n):
		if s[n - i - 1] == '1':
			last = n - i
			break
	if first == 1:
		sum_ -= 1
	if last == n:
		sum_ -= 10
	flag = True
	if k >= n - last and last != n:
		k -= n - last
		sum_ -= 10
		if last == 1:
			sum_ += 1
		if first == last:
			flag = False
	if k >= first - 1 and first != 1 and flag and (first != n):
		sum_ -= 1
	print(sum_)
for i in range(t):
	solve(i + 1)


from collections import Counter

def main():
	(n, k) = map(int, input().split())
	s = input()
	ori = 0
	one = 0
	zero = 0
	o = []
	z = []
	for i in range(n):
		if s[i] == '0':
			zero += 1
			z.append(i)
		else:
			one += 1
			o.append(i)
	ori = one * 11
	if ori == 0:
		return 0
	flag1 = True
	flag2 = True
	if s[0] == '1':
		ori -= 1
		flag1 = False
	if s[-1] == '1':
		ori -= 10
		flag2 = False
		one -= 1
		o.pop()
	if one == 0:
		return ori
	if flag1 or flag2:
		if one == 1:
			i = o[0]
			if flag2:
				req = n - 1 - i
				if k >= req:
					if i == 0:
						return ori - 9
					return ori - 10
			if flag1:
				req = i
				if k >= req:
					return ori - 1
			return ori
		else:
			i = o[0]
			j = o[-1]
			if flag2:
				req2 = n - 1 - j
				if k >= req2:
					ori -= 10
					k -= req2
			if flag1:
				req1 = i
				if k >= req1:
					ori -= 1
			return ori
	return ori
for _ in range(int(input())):
	print(main())


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = input()
	sh = 0
	pe = 0
	p = 0
	for j in range(n):
		if a[j] == '1':
			sh += 1
			if sh == 1:
				pe = j
				p = j
			else:
				p = j
	minus = 0
	if sh > 0:
		if p + k >= n - 1:
			k = p + k - (n - 1)
			minus += 10
		if sh > 1 or minus == 0:
			if k >= pe:
				minus += 1
		print(sh * 11 - minus)
	else:
		print(0)


from sys import stdin
input = stdin.readline
import bisect
import math

def calc(l):
	ans = 0
	for i in range(len(l) - 1):
		ans += int(l[i]) * 10 + int(l[i + 1])
	return ans
for xoxo in range(1):
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input()
		l = list(s)
		l = l[:n]
		ind = []
		x = []
		for i in range(n):
			if int(s[i]) == 1:
				ind.append(i)
		if len(ind) == 0:
			print(0)
			continue
		elif len(ind) == 1:
			x.append(n - ind[0] - 1)
			x.append(ind[0])
			if k >= x[0]:
				(l[-1], l[ind[0]]) = (l[ind[0]], l[-1])
			elif k >= x[1]:
				(l[0], l[ind[0]]) = (l[ind[0]], l[0])
		else:
			x.append(n - ind[-1] - 1)
			x.append(ind[0])
			x.append(sum(x))
			if k >= x[2]:
				(l[-1], l[ind[-1]]) = (l[ind[-1]], l[-1])
				(l[0], l[ind[0]]) = (l[ind[0]], l[0])
			elif k >= x[0] and x[0] != 0:
				(l[-1], l[ind[-1]]) = (l[ind[-1]], l[-1])
			elif k >= x[1]:
				(l[0], l[ind[0]]) = (l[ind[0]], l[0])
		print(calc(l))


import sys

def f(s):
	c = 0
	for i in range(len(s) - 1):
		c += int(str(s[i]) + str(s[i + 1]))
	return c

def aux(n, k, s):
	i = n - 1
	while i >= 0 and s[i] != 1:
		i -= 1
	if i < 0:
		return 0
	elif i == 0:
		if k >= n - 1:
			(s[i], s[-1]) = (s[-1], s[i])
			return f(s)
		return f(s)
	else:
		if k >= n - 1 - i:
			(s[i], s[-1]) = (s[-1], s[i])
			k -= n - 1 - i
		j = 0
		while j < n and s[j] != 1:
			j += 1
		if j == n - 1:
			return f(s)
		else:
			if k >= j:
				(s[j], s[0]) = (s[0], s[j])
				return f(s)
			return f(s)

def main():
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 6)
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		s = list(map(int, list(input().replace('\n', ''))))
		print(aux(n, k, s))
main()


for h in range(int(input())):
	(n, k) = map(int, input().split())
	u = input()
	x = []
	for i in u:
		x.append(i)
	c = x.count('1') * 11
	if c == 0:
		print(c)
		continue
	if x[-1] == '0':
		m = 0
		for i in range(n):
			if x[i] == '1':
				m = i
		if k >= n - m - 1:
			(x[m], x[-1]) = (x[-1], x[m])
			k = k - (n - m - 1)
			c -= 10
	else:
		c -= 10
	if x[0] == '0':
		m = n
		for i in range(n):
			if x[i] == '1':
				break
		if k >= i and i != n - 1:
			k -= i
			c -= 1
	else:
		c -= 1
	print(c)


from sys import stdin, stdout
I = stdin.readline
O = stdout.write
for _ in range(int(I())):
	(n, k) = list(map(int, I().split()))
	st = I()
	la = -k
	st = list(st)
	ans = 0
	if st.count('1') == 0:
		print(0)
		continue
	for j in range(n - 1, -1, -1):
		if st[j] == '1':
			la = j
			break
	if k >= n - 1 - la:
		st[la] = '0'
		st[n - 1] = '1'
		k -= n - 1 - la
	s = 0
	for i in range(n - 1):
		if st[i] == '1':
			now = i - s
			if k >= now:
				k -= now
				st[i] = '0'
				st[s] = '1'
				s += 1
	for i in range(n - 1):
		ans += int(st[i] + st[i + 1])
	print(ans)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = list(input())
	l = []
	ans = 0
	t = s.count('1')
	if t == 0:
		print(0)
		continue
	for i in range(n):
		if s[i] == '1':
			l.append(i)
			ans += 11
	used = 0
	if k >= n - l[-1] - 1:
		k -= n - l[-1] - 1
		used = 1
		ans -= 10
	if k >= l[0] and (used == 0 or t > 1):
		ans -= 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	s = list(input())
	(ones, leftmost, rightmost) = (0, n, -1)
	for i in range(n):
		if s[i] == '1':
			ones += 1
			if leftmost == n:
				leftmost = i
			rightmost = i
	ans = 0
	if ones > 0 and n - rightmost - 1 <= x:
		x -= n - rightmost - 1
		ans += 1
		ones -= 1
	if ones > 0 and leftmost <= x:
		ans += 10
		ones -= 1
	ans += 11 * ones
	print(ans)


tc = int(input())
for t in range(tc):
	(n, k) = map(int, input().split())
	st = input()
	one = 0
	s = n + 100
	e = 0
	for i in range(n):
		if st[i] == '1':
			one = one + 1
			if s == n + 100:
				s = i
			e = i
	sm = 0
	if one > 0 and n - 1 - e <= k:
		sm = 1
		one = one - 1
		k = k - (n - 1 - e)
	if one > 0 and s <= k:
		sm = sm + 10
		one = one - 1
	print(sm + 11 * one)


t = int(input())
for e in range(t):
	(n, k) = map(int, input().split())
	a = input()
	(l, r) = (-1, -1)
	s = 0
	for i in range(n):
		if a[i] == '1':
			s += 11
			r = i
			if l == -1:
				l = i
	if r == -1:
		print(s)
		continue
	f = k
	if k >= n - r - 1:
		s -= 10
		f -= n - r - 1
	if l != r or k < n - r - 1:
		if f >= l:
			s -= 1
	print(s)


for _ in [0] * int(input()):
	(n, k) = map(int, input().split())
	s = input()
	one = s.count('1')
	if one == 0:
		print(0)
		continue
	if one == 1:
		for i in range(n):
			if s[i] == '1':
				index = i
				break
		if n - 1 - index <= k:
			print(1)
			continue
		print(11 - (index <= k))
		continue
	for i in range(n):
		if s[i] == '1':
			index_1 = i
			break
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			index_2 = i
			break
	if n - 1 - index_2 <= k:
		print(11 * one - 10 - (index_1 <= k - n + index_2 + 1))
		continue
	print(11 * one - (index_1 <= k))


def solve():
	(n, k) = map(int, input().split())
	s = list(input())
	indl = -1
	indr = -1
	for i in range(n):
		if s[i] == '1':
			indl = i
			break
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			indr = i
			break
	ans = 0
	if indl != -1:
		if n - 1 - indr <= k:
			k -= n - 1 - indr
			ans += 1
			del s[indr]
			if s.count('1') == 0:
				print(1)
				return
		k -= indl
		if k >= 0:
			ans += 10
			del s[indl]
		ans += s.count('1') * 11
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	(p1, p2, ans) = (-1, -1, 0)
	for i in range(n):
		if a[i] == '1':
			ans += 11
			p2 = i
			if p1 == -1:
				p1 = i
	if p2 == -1:
		print(ans)
		continue
	if k >= n - 1 - p2:
		ans -= 10
		if p1 != p2 or k < n - p2 - 1:
			if k - (n - p2 - 1) >= p1:
				ans -= 1
				print(ans)
				continue
			else:
				print(ans)
				continue
	if p1 != p2 or k < n - p2 - 1:
		if k >= p1:
			ans -= 1
	print(ans)


from posixpath import split

def Calculate(num):
	return num * 11

def count_left_most_one(ara, sz):
	for x in range(sz):
		if ara[x] == '1':
			return x
	return -1

def count_right_most_one(ara, sz):
	cnt = 0
	for x in range(sz - 1, -1, -1):
		if ara[x] == '1':
			return cnt
		cnt += 1
	return -1
t = int(input())
for balsal in range(t):
	x = input()
	x = x.split(' ')
	n = int(x[0])
	k = int(x[1])
	ara = input()
	x = count_left_most_one(ara, n)
	y = count_right_most_one(ara, n)
	num = ara.count('1')
	if num > 1:
		ans = 11 * (num - 1)
		if y <= k:
			if y + x > k:
				ans += 1
		else:
			ans += 10
			if x > k:
				ans += 1
	elif num == 1:
		if k < 1:
			if x != 0 and y != 0:
				ans = 11
			elif x == 0:
				ans = 10
			elif y == 0:
				ans = 1
		elif len(ara) == 1:
			ans = 1
		elif k >= y:
			ans = 1
		elif k >= x:
			ans = 10
		else:
			ans = 11
	else:
		ans = 0
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	mas = list(input())
	d = dict()
	d['1'] = []
	d['0'] = []
	for i in range(n):
		d[mas[i]].append(i)
	if len(d['1']) == 0:
		print(0)
	elif len(d['1']) == 1:
		ans = 11
		index = d['1'][0]
		if n - index - 1 <= k:
			ans -= 10
		elif index <= k:
			ans -= 1
		print(ans)
	else:
		ans = len(d['1']) * 11
		r = max(d['1'])
		l = min(d['1'])
		if n - r - 1 <= k:
			ans -= 10
			k -= n - r - 1
		if l <= k:
			ans -= 1
			k -= l
		print(ans)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	s = input()
	cnt = 0
	for c in s:
		if c == '1':
			cnt += 1
	if cnt == 0:
		print(0)
		continue
	ans = cnt * 11
	(left, right) = (0, n - 1)
	while s[left] == '0':
		left += 1
	while s[right] == '0':
		right -= 1
	if k >= left + n - 1 - right and left != right:
		ans -= 11
	elif k >= n - 1 - right:
		ans -= 10
	elif k >= left:
		ans -= 1
	print(ans)


loopcount = int(input())
for loop in range(loopcount):
	x = input()
	x = x.split(' ')
	x = list(map(int, x))
	a = input()
	output = 0
	first = -1
	last = -1
	for i in range(x[0]):
		if a[i] == '1':
			output += 11
			last = i
			if first == -1:
				first = i
	if first == -1:
		print(output)
		continue
	if first == last:
		if x[0] - 1 - last <= x[1]:
			output -= 10
			x[1] -= x[0] - 1 - last
		elif last <= x[1]:
			output -= 1
	else:
		if x[0] - 1 - last <= x[1]:
			output -= 10
			x[1] -= x[0] - 1 - last
		if first <= x[1]:
			output -= 1
	print(output)


for t in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	first = -1
	last = n
	ctr = 0
	for i in range(n):
		if s[i] == '1':
			if first == -1:
				first = i
			last = i
			ctr += 1
	if ctr == 0:
		print(0)
	elif ctr == 1:
		if n - 1 - last <= k:
			print(1)
		elif first <= k:
			print(10)
		else:
			print(11)
	else:
		total = 0
		if n - 1 - last <= k:
			total += 1
			ctr -= 1
			k -= n - 1 - last
		if first <= k:
			total += 10
			ctr -= 1
		total += ctr * 11
		print(total)


for y in [0] * int(input()):
	(n, k) = map(int, input().split())
	s = input()
	(i, j) = (x.find('1') % 8 ** 10 for x in (s, s[::-1]))
	print(11 * s.count('1') - (k >= i + j < n - 1 or i <= k < j) - 10 * (j <= k))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = list(input())
	answ = 0
	i = n - 1
	while i >= 0 and s[i] != '1':
		i -= 1
	if i == -1:
		print(0)
		continue
	if n - i - 1 <= k:
		k -= n - i - 1
		(s[i], s[-1]) = (s[-1], s[i])
	i = 0
	while i < n - 1 and s[i] != '1':
		i += 1
	if i != n - 1 and k >= i:
		(s[0], s[i]) = (s[i], s[0])
	print(int(s[0]) * 10 + 11 * s[1:-1].count('1') + int(s[-1]))


def spliter():
	d = input()
	a = d.split()
	r = []
	for i in a:
		k = int(i)
		r.append(k)
	return r
_t = int(input())
for _ in range(_t):
	n = spliter()
	a = input()
	count1 = -1
	count2 = -1
	count3 = 0
	for i in range(n[0]):
		if a[i] == '1':
			if count3 == 0:
				count1 = i
			count2 = n[0] - i - 1
			count3 += 1
	if count2 <= n[1]:
		n[1] -= count2
		count2 = 0
	if count1 <= n[1]:
		count1 = 0
	if count3 == 0:
		print(0)
		continue
	elif count3 == 1:
		if count2 == 0:
			print(1)
		elif count1 == 0:
			print(10)
		else:
			print(11)
	else:
		resul = 11 * count3
		if count1 == 0:
			resul -= 1
		if count2 == 0:
			resul -= 10
		print(resul)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(first, last, cnt, ans) = (n, 0, 0, 0)
	for i in range(n):
		if s[i] == '0':
			continue
		cnt += 1
		if first == n:
			first = i
		last = i
	if cnt and n - last - 1 <= k:
		ans += 1
		cnt -= 1
		k -= n - last - 1
	if cnt and first <= k:
		ans += 10
		cnt -= 1
	ans += 11 * cnt
	print(ans)


from collections import defaultdict
t = int(input())
while t > 0:
	t -= 1
	(n, k) = [int(x) for x in input().split(' ')]
	s = input()
	one_count = 0
	if len(s) == 1:
		print(int(s))
		continue
	for letter in s:
		if letter == '1':
			one_count += 1
	answer = one_count * 11
	if s[0] == '1':
		answer -= 1
	if s[n - 1] == '1':
		answer -= 10
	if k == 0 or one_count == 0:
		print(answer)
		continue
	starting_gap = 0
	while s[starting_gap] != '1':
		starting_gap += 1
	ending_gap = 0
	while s[n - 1 - ending_gap] != '1':
		ending_gap += 1
	if ending_gap != 0 and ending_gap <= k:
		answer -= 10
		k -= ending_gap
	if starting_gap != 0 and starting_gap <= k:
		answer -= 1
	print(max(1, answer))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	(back, front) = (-1, -1)
	cnt = -1
	s = list(s)
	for i in range(n - 1, -1, -1):
		cnt += 1
		if s[i] == '1':
			ind1 = i
			front = cnt
			break
	cnt = -1
	for i in range(n):
		cnt += 1
		if s[i] == '1':
			ind2 = i
			back = cnt
			break
	if front == -1:
		print(0)
		continue
	elif ind1 == ind2:
		if k >= front:
			print(1)
			continue
		elif k >= back:
			print(10)
			continue
		else:
			print(11)
	else:
		if k >= front:
			(s[ind1], s[-1]) = (s[-1], s[ind1])
			k -= front
		if k >= back:
			(s[ind2], s[0]) = (s[0], s[ind2])
		res = 0
		if s[0] == '1':
			res += 10
		if s[-1] == '1':
			res += 1
		for i in range(1, n - 1):
			if s[i] == '1':
				res += 11
		print(res)


def solve():
	(n, k) = map(int, input().split())
	inp = input()
	ones = inp.count('1')
	if ones == 0:
		return 0
	front = inp.find('1')
	end = inp[::-1].find('1')
	if ones == 1:
		if k >= end:
			return 1
		if k >= front:
			return 10
		return 11
	inp = list(inp)
	if k >= end != 0:
		k -= end
		inp[len(inp) - end - 1] = '0'
		inp[-1] = '1'
	if k >= front != 0:
		inp[0] = '1'
		inp[front] = '0'
	res = 0
	for i in range(len(inp) - 1):
		res += int(inp[i] + inp[i + 1])
	return res

def main():
	for _ in range(int(input())):
		print(solve())
	return
main()


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(left, right, ans) = (0, 0, 0)
	for i in range(n - 1):
		ans += int(s[i] + s[i + 1])
	if ans == 0:
		print(0)
		continue
	for i in s:
		if i == '1':
			break
		left += 1
	for i in s[::-1]:
		if i == '1':
			break
		right += 1
	if left + right == n - 1:
		if right <= k and right != 0:
			k -= right
			ans = 1
			right = 0
		elif left <= k and right != 0 and (left != 0):
			k -= left
			ans = 10
	else:
		if right <= k and right != 0:
			k -= right
			ans -= 10
			right = 0
		if left <= k and left != 0:
			k -= left
			ans -= 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	f = 999999999
	l = -999999999
	ans = 0
	for i in range(n):
		if s[i] == '1':
			f = min(f, i)
			l = max(l, i)
			ans += 11
	l = n - 1 - l
	used = 0
	if k >= l:
		ans -= 10
		k -= l
		used = 1
	if k >= f and (used == 0 or ans > 11):
		ans -= 1
	print(ans)


def substringSum(s):
	sum = 0
	for i in range(1, len(s)):
		sum += int(s[i - 1] + s[i])
	return sum

def solution(n, s, k):
	min_idx = s.index('1')
	max_idx = -1
	for (idx, x) in enumerate(s):
		if s[idx] == '1':
			max_idx = idx
	sum = substringSum(s)
	if k == 0:
		print(sum)
	else:
		rightShift = False
		if k >= n - 1 - max_idx and max_idx != n - 1:
			sum -= 10 - (max_idx == 0)
			k -= n - 1 - max_idx
			rightShift = True
		if (min_idx != max_idx or (not rightShift and min_idx != n - 1)) and 1 <= min_idx <= k:
			sum -= 1
			k -= min_idx
		print(sum)
T = int(input())
for t in range(T):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	if '1' not in s:
		print('0')
	else:
		solution(n, s, k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input()))
	i = 0
	j = n - 1
	while j >= 0:
		if l[j] == 0:
			pass
		else:
			if k >= n - 1 - j:
				k -= n - 1 - j
				l[j] = 0
				l[-1] = 1
			break
		j -= 1
	while i <= n - 2:
		if l[i] == 0:
			pass
		elif k >= i:
			k -= i
			l[i] = 0
			l[0] = 1
			break
		i += 1
	ans = 0
	for i in range(n - 1):
		ans += l[i] * 10 + l[i + 1]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	z = sum((11 * int(c) for c in s))
	k = min(k, n - 1)
	(a, b) = (0, 0)
	while a <= k:
		if s[-a - 1] == '1':
			break
		a += 1
	while b <= k:
		if s[b] == '1':
			break
		b += 1
	if b + a == n - 1 == k:
		print(z - 10)
	elif b + a <= k:
		print(z - 11)
	elif a <= k:
		print(z - 10)
	elif b <= k:
		print(z - 1)
	else:
		print(z)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	st = input()
	minsum = 11 * st.count('1')
	if minsum == 0:
		print(0)
		continue
	ones = st.count('1')
	first = st.index('1')
	last = st[::-1].index('1')
	if last <= k:
		k -= last
		minsum -= 10
	if first <= k and minsum > 1:
		k -= first
		minsum -= 1
	print(minsum)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	L = list(input())
	L = [int(x) for x in L]
	if not 1 in L:
		print(0)
		continue
	if L.count(1) == 1:
		a = L.index(1)
		if k >= n - 1 - a:
			print(1)
		elif k >= a:
			print(10)
		else:
			print(11)
		continue
	a = L.index(1)
	L.reverse()
	b = L.index(1)
	b = n - b - 1
	c = L.count(1)
	if k >= n - 1 - b + a:
		ans = c * 11 - 11
	elif k >= n - 1 - b:
		ans = c * 11 - 10
	elif k >= a:
		ans = c * 11 - 1
	else:
		ans = c * 11
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	for i in range(n - 1):
		count += int(s[i] + s[i + 1])
	if count == 0:
		print(0)
		continue
	if s[n - 1] != '1':
		right = n - 1
		while s[right] != '1':
			right -= 1
		k -= n - 1 - right
		if k >= 0:
			count -= 10
			if right == 0:
				count += 1
		else:
			k += n - 1 - right
	if s[0] != '1' and count != 1:
		left = 0
		while s[left] != '1':
			left += 1
		k -= left
		if left != n - 1 and k >= 0:
			count -= 1
	print(count)


def func(s):
	ans = 0
	for i in range(len(s) - 1):
		ans += int(s[i:i + 2])
	return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	lone = 0
	rone = 0
	for i in range(n):
		if s[i] == '1':
			lone = i
			break
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			rone = i
			break
	right = False
	left = False
	if rone != n - 1:
		if n - 1 - rone <= k:
			right = True
			k -= n - 1 - rone
	if right:
		if rone != lone:
			if lone != 0:
				if lone <= k:
					left = True
	elif lone != 0:
		if lone <= k:
			left = True
	ans = func(s)
	if ans == 0:
		print(0)
		continue
	if right:
		ans -= 10
		if rone == 0:
			ans += 1
	if left:
		ans -= 1
		if lone == n - 1:
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = (int(number) for number in input().split(' '))
	item = 0
	zero_count_right = 0
	zero_count_left = 0
	ones = 0
	zeros = 0
	for number in input():
		if item == 0:
			if number == '1':
				left = 1
				count_left = False
			else:
				left = 0
				count_left = True
		if number == '0':
			zeros += 1
			zero_count_right += 1
			if count_left is True:
				zero_count_left += 1
		else:
			ones += 1
			zero_count_right = 0
			count_left = False
		item += 1
	sum_row = ones * 11
	if ones >= 1 and zero_count_right <= k:
		sum_row -= 10
		ones -= 1
		k -= zero_count_right
	if ones >= 1 and zero_count_left <= k:
		sum_row -= 1
	print(sum_row)


def count(l):
	ans = 0
	n = len(l)
	for i in range(n - 1):
		if l[i] == '0' and l[i + 1] == '0':
			continue
		elif l[i] == '0' and l[i + 1] == '1':
			ans += 1
			continue
		elif l[i] == '1' and l[i + 1] == '0':
			ans += 10
			continue
		else:
			ans += 11
	return ans

def ss(n, l, k):
	f = 0
	if l[-1] == '0':
		for i in range(n - 2, -1, -1):
			if l[i] == '1':
				s = n - i - 1
				if s <= k:
					k -= s
					l[i] = '0'
					l[-1] = '1'
					f = 1
				break
	if l[-1] == '1':
		f = 1
	if f == 1 and l.count('1') == 1:
		return count(l)
	if l[0] == '0':
		for i in range(1, n):
			if l[i] == '1':
				s = i
				if s <= k:
					k -= s
					l[i] = '0'
					l[0] = '1'
					f = 1
				break
	return count(l)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(str(input()))
	print(ss(n, l, k))


import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	(n, k) = map(int, input().split())
	s = input()
	s = list(s)
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			if k >= n - i - 1:
				(s[n - 1], s[i]) = (s[i], s[n - 1])
				k -= n - 1 - i
			break
	for i in range(n - 1):
		if s[i] == '1':
			if k >= i:
				(s[0], s[i]) = (s[i], s[0])
				k -= i
	ans = 0
	for i in range(n - 1):
		num = int(s[i] + s[i + 1])
		ans += num
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


def fun(l):
	n = len(l)
	c = 0
	for i in range(n - 1):
		c += int(l[i] + l[i + 1])
	return c
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input().rstrip()
	l = [x for x in s]
	for i in range(n - 1, -1, -1):
		if l[i] == '1':
			if k >= n - 1 - i:
				(l[i], l[n - 1]) = (l[n - 1], l[i])
				k -= n - 1 - i
			break
	for i in range(n - 1):
		if l[i] == '1':
			if k >= i:
				(l[0], l[i]) = (l[i], l[0])
				k -= i
			break
	ans2 = fun(l)
	print(ans2)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	tot = 0
	f = k
	last = first = 0
	if s[-1] != '1':
		for i in range(n - 2, -1, -1):
			if k == 0:
				break
			if s[i] == '1':
				(s[i], s[-1]) = (s[-1], s[i])
				last = 1
				k -= 1
				break
			k -= 1
	if not last:
		k = f
	if s[0] != '1':
		for i in range(1, n - 1):
			if k == 0:
				break
			if s[i] == '1':
				(s[0], s[i]) = (s[i], s[0])
				break
			k -= 1
	for i in range(n):
		num = s[i]
		if num == '0':
			continue
		if i == 0:
			tot += 10
		elif i == n - 1:
			tot += 1
		else:
			tot += 11
	print(tot)


import math as m
from collections import defaultdict, deque
from bisect import bisect_left as b_l
from bisect import bisect_right as b_r
for _ in range(int(input())):
	(n, k) = (int(i) for i in input().split())
	s = input()
	ans = 0
	for i in range(n - 1):
		ans += int(s[i] + s[i + 1])
	start = 0
	while start < n and s[start] != '1':
		start += 1
	end = n - 1
	while end > -1 and s[end] != '1':
		end -= 1
	flag = True
	if end != -1 and end != n - 1:
		if n - 1 - end <= k:
			if start == end:
				ans = 1
				k -= n - 1 - end
				flag = False
			else:
				ans -= 10
				k -= n - 1 - end
	if start != n and flag and (start != 0) and (start != n - 1):
		if start <= k:
			ans -= 1
	print(ans)


T = int(input())
while T:
	T -= 1
	(n, k) = [int(x) for x in input().split(' ')]
	a = list(input())
	l = -1
	c = -1
	cnt = 0
	for i in range(len(a)):
		if a[i] == '0':
			continue
		c = i
		cnt += 1
		if l == -1:
			l = i
	r = c
	if l == -1 and r == -1:
		print(0)
	elif l == r:
		if n - r - 1 <= k:
			print(1)
		elif l <= k:
			print(10)
		else:
			print(11)
	else:
		ans = 0
		if n - r - 1 <= k:
			ans += 1
			if l <= k - n + r + 1:
				ans += 10
			else:
				ans += 11
		else:
			ans += 11
			if l <= k:
				ans += 10
			else:
				ans += 11
		ans += (cnt - 2) * 11
		print(ans)


T = int(input())
for case in range(T):
	(n, k) = map(int, input().split())
	s = input()
	if '1' not in s:
		print(0)
		continue
	ans = 0
	for i in range(n - 1):
		ans += int(s[i:i + 2])
	(l, r) = (s.find('1'), s.rfind('1'))
	if 0 < n - 1 - r <= k:
		if r == 0:
			ans -= 9
		else:
			ans -= 10
			k -= n - 1 - r
			if l != r and 0 < l <= k:
				ans -= 1
	elif 0 < l <= k:
		if l != n - 1:
			ans -= 1
	print(ans)


def task(n, k, s):
	total = 0
	for i in range(n - 1):
		value = int(s[i:i + 2])
		total += value
	ones = 0
	for c in s:
		if c == '1':
			ones += 1
	startzeros = 0
	for c in s:
		if c == '0':
			startzeros += 1
		else:
			break
	endzeros = 0
	for c in s[::-1]:
		if c == '0':
			endzeros += 1
		else:
			break
	if ones > 0:
		if endzeros > 0:
			if endzeros <= k:
				k -= endzeros
				if ones == 1 and startzeros == 0:
					total -= 9
				else:
					total -= 10
				ones -= 1
		else:
			ones -= 1
	if ones > 0 and startzeros > 0 and (startzeros <= k):
		total -= 1
	print(total)
t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	s = input()
	task(n, k, s)


import collections
t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	a = list(input())
	for i in range(n):
		a[i] = int(a[i])
	if a[n - 1] == 0:
		j = n - 2
		flag = False
		while j >= 0:
			if a[j] == 1:
				flag = True
				break
			j -= 1
		if flag:
			if abs(j - (n - 1)) <= k:
				k -= abs(j - (n - 1))
				(a[j], a[n - 1]) = (a[n - 1], a[j])
	if a[0] == 0:
		j = 1
		flag = False
		while j <= n - 2:
			if a[j] == 1:
				flag = True
				break
			j += 1
		if flag:
			if abs(j - 0) <= k:
				k -= abs(j - 0)
				(a[0], a[j]) = (a[j], a[0])
	s = 0
	s += a[-1]
	s += 10 * a[0]
	for i in range(1, n - 1):
		s += 11 * a[i]
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	beg = s.find('1')
	if beg == -1:
		print(0)
		continue
	endix = s.rfind('1')
	end = n - endix - 1
	s = list(s)
	if k >= end:
		if s.count('1') == 1:
			print(1)
			continue
		s[endix] = '0'
		s[n - 1] = '1'
		k -= end
	if k >= beg:
		s[beg] = '0'
		s[0] = '1'
	ans = 0
	s = ''.join(s)
	for i in range(n - 1):
		ans += int(s[i:i + 2])
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input()))
	fs = 0
	for i in range(n - 1):
		fs += 10 * s[i] + s[i + 1]
	if k == 0:
		print(fs)
	elif s.count(1) == 0:
		print(0)
	elif s.count(1) == 1:
		zf = s.index(1)
		s1 = s[:]
		s1.reverse()
		ze = s1.index(1)
		if ze <= k:
			print(1)
		elif zf <= k:
			print(10)
		else:
			print(11)
	else:
		zf = s.index(1)
		s1 = s[:]
		s1.reverse()
		ze = s1.index(1)
		if 0 < zf + ze <= k:
			if zf > 0 and ze > 0:
				print(fs - 11)
			elif ze > 0:
				print(fs - 10)
			elif zf > 0:
				print(fs - 1)
		elif 0 < ze <= k:
			print(fs - 10)
		elif 0 < zf <= k:
			print(fs - 1)
		else:
			print(fs)


num = int(input())

def counter(array):
	res = 0
	for i in range(len(array) - 1):
		res += array[i] * 10 + array[i + 1]
	return res
for _ in range(num):
	(n, k) = map(int, input().split())
	array = list(map(int, list(input())))
	answer = counter(array)
	if k > 0:
		if array[n - 1] == 0:
			count = 0
			for i in range(n - 1, 0, -1):
				if array[i] == 1:
					break
				count += 1
			if count <= k and answer >= 10:
				k -= count
				answer -= 10
				if answer == 0:
					answer += 1
		if array[0] == 0:
			count = 0
			for i in range(n - 1):
				if array[i] == 1:
					break
				count += 1
			if count <= k and answer > 1:
				k -= count
				answer -= 1
	print(answer)


t = int(input())
for k in range(t):
	(n, k) = map(int, input().split(' '))
	s1 = input()
	s = []
	ones = 0
	for i in s1:
		if i == '1':
			ones += 1
		s.append(int(i))
	fone = 0
	for i in range(n):
		if s[i] == 1:
			fone = i
			break
	lone = 0
	for i in range(n - 1, -1, -1):
		if s[i] == 1:
			lone = i
			break
	add = 0
	if ones > 0 and k >= n - lone - 1:
		add += 1
		ones -= 1
		k -= n - lone - 1
	if ones > 0 and k >= fone:
		add += 10
		ones -= 1
		k -= fone
	temp = 0
	print(11 * ones + add)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(ans, f, l, o) = (0, n, -1, 0)
	for i in range(n):
		if s[i] == '0':
			continue
		o += 1
		if f == n:
			f = i
		l = i
	if o and n - l - 1 <= k:
		ans += 1
		o -= 1
		k -= n - l - 1
	if o and f <= k:
		ans += 10
		o -= 1
	ans += 11 * o
	print(ans)