You are given a string S of length N, which consists of digits from 0 to 9. You can apply the following operation to the string:

Choose an integer L with 1≤ L ≤ N and apply S_{i} = (S_{i} + 1) \mod 10 for each 1 ≤ i ≤ L.

For example, if S=39590, then choosing L=3 and applying the operation yields the string S=\underline{406}90.

The prefix of string S of length l\;(1 ≤ l ≤ \mid S \mid ) is string S_{1} S_{2} \dots S_{l}. A prefix of length l is called good if S_{1}=0, S_{2}=0, \dots, S_{l}=0. Find the length of the longest good prefix that can be obtained in string S by applying the given operation maximum K times.

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of test cases. The T test cases then follow:
- The first line of each test case contains two space-separated integers N, K.
- The second line of each test case contains the string S.

------ Output Format ------ 

For each test case, output in a single line the length of the longest good prefix that can be obtained in string S by applying the given operation maximum K times.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ K ≤ 10^{9}$
$\mid S \mid = N$
$S$ contains digits from $0$ to $9$
- Sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$.

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
6
3 5
380
3 9
380
4 2
0123
5 13
78712
6 10
051827
8 25
37159725

----- Sample Output 1 ------ 
0
3
1
3
2
5

----- explanation 1 ------ 
Test case $1$: There is no way to obtain zeros on the prefix of the string $S = 380$ by applying the given operation maximum $5$ times.

Test case $2$: The optimal strategy is: choose $L = 2$ and apply the operation twice, resulting in $S=500$, then choose $L = 1$ and apply the operation $5$ times, resulting in $S=000$.

Test case $4$: One of the possible sequence of operations is the following:
- Choose $L = 5$ and apply the operation thrice, resulting in $S=01045$.
- Choose $L = 2$ and apply the operation $9$ times, resulting in $S=90045$. 
- Choose $L = 1$ and apply the operation once, resulting in $S=00045$.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
def solve(n, k, arr):

	def moves_needed(m):
		offset = 0
		for i in range(m, -1, -1):
			num = (arr[i] + offset) % 10
			if num != 0:
				offset += 10 - num
		return offset
	l = 0
	r = n - 1
	while l < r:
		m = (l + r) // 2
		if moves_needed(m) > k:
			r = m
		else:
			l = m + 1
	if l == n - 1 and moves_needed(n - 1) <= k:
		return n
	return l
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input()))
	print(solve(n, k, arr))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(input())
	(low, high) = (0, n + 1)
	while high - low > 1:
		mid = low + (high - low) // 2
		ck = 0
		for i in range(mid - 1, -1, -1):
			temp = (ck + int(l[i])) % 10
			if temp != 0:
				ck += 10 - temp
		if ck <= k:
			low = mid
		else:
			high = mid
	print(low)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = [k]
	m = int(k / 10)
	t = 0
	for i in range(n):
		remainder = a[i] % 10
		diff = 10 - int(s[i])
		if remainder < diff:
			num = diff + (m - 1) * 10
			m = int(num / 10)
			if num < 0:
				t = 1
				break
			else:
				a.append(num)
		else:
			num = diff + m * 10
			a.append(num)
			m = int(num / 10)
	if t == 1:
		print(i)
	else:
		print(n)


def snek(x):
	f = 0
	for i in range(len(x) - 1, -1, -1):
		z = int(x[i])
		z = (z + f % 10) % 10
		f += (10 - z) % 10
	return f
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	l = 0
	h = len(s) - 1
	r = False
	while l <= h:
		m = (l + h) // 2
		f = snek(s[:m + 1])
		if f > k:
			h = m - 1
		elif f <= k:
			l = m + 1
	if not r:
		print(h + 1)


def calculate_flips(ss):
	flips = 0
	for i in range(len(ss) - 1, -1, -1):
		num = int(ss[i])
		num = (num + flips % 10) % 10
		flips += (10 - num) % 10
	return flips
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	lo = 0
	hi = len(s) - 1
	res = False
	while lo <= hi:
		mid = (lo + hi) // 2
		flips = calculate_flips(s[:mid + 1])
		if flips > k:
			hi = mid - 1
		elif flips <= k:
			lo = mid + 1
	if not res:
		print(hi + 1)


GI = lambda : int(input())
GIS = lambda : map(int, input().split())
LGIS = lambda : list(GIS())

def main():
	for t in range(GI()):
		(n, k) = GIS()
		s = input()
		print(solve(n, k, s))

def solve(n, k, s):
	l = -1
	r = n - 1
	while l < r:
		m = (l + r + 1) // 2
		if can_prefix_from(s, m, k):
			l = m
		else:
			r = m - 1
	return l + 1

def can_prefix_from(s, i, k):
	rotations = 0
	for i in range(i, -1, -1):
		rotated_value = (int(s[i]) + rotations) % 10
		need_to_rotate = (10 - rotated_value) % 10
		if need_to_rotate > k:
			return False
		k -= need_to_rotate
		rotations += need_to_rotate
	return True
main()


import math

def calc(s, n, k):
	ops = 0
	ii = n - 1
	while ii >= 0:
		if (int(s[ii]) + ops) % 10 != 0:
			ops += 10 - (int(s[ii]) + ops) % 10
		ii -= 1
	return ops

def main():
	t = int(input())
	while t > 0:
		(n, k) = map(int, input().split())
		s = input()
		l = 0
		h = n + 1
		while h - l > 1:
			mid = (l + h) // 2
			val = calc(s, mid, k)
			if val <= k:
				l = mid
			else:
				h = mid
		print(l)
		t -= 1
main()


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	ans = 0
	for c in s:
		req = (10 - int(c)) % 10
		if req > k:
			break
		ans += 1
		k = int((k - req) / 10) * 10 + req
	print(ans)


def costf(x):
	add = 0
	x1 = 0
	while x >= 0:
		if (int(s[x]) + add) % 10 == 0:
			x -= 1
		else:
			x1 = x1 + (10 - (int(s[x]) + add) % 10)
			add += 10 - (int(s[x]) + add) % 10
			x -= 1
	return x1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	lp = 0
	l = 0
	h = n - 1
	while l <= h:
		m = (l + h) // 2
		cost = costf(m)
		if cost > k:
			h = m - 1
		elif cost <= k:
			lp = m + 1
			l = m + 1
	print(lp)


def countOps(S, L):
	ret = 0
	for i in range(L - 1, -1, -1):
		ret += (10 - (int(S[i]) + ret) % 10) % 10
	return ret

def main():
	T = int(input())
	for _ in range(T):
		(N, K) = [int(w) for w in input().split()]
		S = input().strip()
		(lo, hi) = (0, N)
		while hi - lo > 1:
			mid = (lo + hi) // 2
			if countOps(S, mid) <= K:
				lo = mid
			else:
				hi = mid - 1
		if countOps(S, hi) > K:
			hi = lo
		print(hi)
main()


from collections import Counter
from math import ceil, floor, log, gcd
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
for _ in range(int(input().strip())):
	(n, k) = inp_multi()
	s = input().strip()
	i = 0
	while i < n:
		t = int(s[i])
		while k > 0 and (k + t) % 10 != 0:
			k -= 1
		if k == 0:
			if t == 0:
				i += 1
				continue
			else:
				break
		i += 1
	print(i)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if n == 1:
		ans = (10 - int(s[0])) % 10
		if ans <= k:
			print(1)
		else:
			print(0)
	elif n == 2:
		a1 = (10 - int(s[1])) % 10
		b = (int(s[0]) + a1) % 10
		a2 = (10 - b) % 10
		if a1 + a2 <= k:
			print(2)
		else:
			a3 = (10 - int(s[0])) % 10
			if a3 <= k:
				print(1)
			else:
				print(0)
	else:
		li = []
		val = (10 - int(s[0])) % 10
		li.append(val)
		a1 = (10 - int(s[1])) % 10
		b = (int(s[0]) + a1) % 10
		a2 = (10 - b) % 10
		li.append(a1 + a2)
		for i in range(2, n):
			c1 = (10 - int(s[i])) % 10
			d = (int(s[i - 1]) + c1) % 10
			c2 = (10 - d) % 10
			c3 = a2
			li.append(c1 + c2 + c3)
			a2 = c2 + c3
		count = 0
		for i in range(len(li)):
			if li[i] <= k:
				count = count + 1
			else:
				break
		print(count)


def f2(z, s, t=0):
	for i in range(z, -1, -1):
		v = (int(s[i]) + t) % 10
		t += 10 - v if v != 0 else 0
	return t
for tcs in range(int(input())):
	(n, k) = map(int, input().split())
	wrd = list(map(int, list(input())))
	(a, x, y) = (0, 0, n - 1)
	while x <= y:
		z = x + (y - x) // 2
		if f2(z, wrd) <= k:
			a = z + 1
			x = a
		else:
			y = z - 1
	print(a)


def f(m, x):
	suma = 0
	for i in range(m, -1, -1):
		v = (int(s[i]) + suma) % 10
		if v == 0:
			continue
		suma += 10 - v
	return suma
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = 0
	r = n - 1
	rj = 0
	while l <= r:
		mid = (l + r) // 2
		if f(mid, s) > k:
			r = mid - 1
		else:
			rj = mid + 1
			l = mid + 1
	print(rj)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	for i in s:
		x = (10 - int(i)) % 10
		t = k - x
		if t < 0:
			break
		k = t // 10 * 10 + x
		c += 1
	print(c)


def solver(n, k, s):
	l = 0
	r = n + 1
	while l < r - 1:
		mid = (l + r) // 2
		count = 0
		for i in range(mid - 1, -1, -1):
			req = (int(s[i]) + count) % 10
			if req != 0:
				count += 10 - req
		if count <= k:
			l = mid
		else:
			r = mid
	print(l)
t = int(input())
while t > 0:
	t -= 1
	(n, k) = list(map(int, input().split(' ')))
	s = input()
	solver(n, k, s)


def f(a, b):
	c = a % 10
	b += a
	b %= 10
	if b == 0:
		return 0
	return 10 - b

def check(ar, l, p):
	i = 0
	for r in range(l, -1, -1):
		j = f(i, ar[r])
		if i + j > p:
			return False
		i += j
	return True
t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	a = input()
	aa = [int(a[i]) for i in range(n)]
	o = 0
	u = n - 1
	ans = 0
	while o <= u:
		if check(aa, (o + u) // 2, k):
			o = (o + u) // 2 + 1
			ans = o
		else:
			u = (o + u) // 2 - 1
	print(ans)


case = int(input())
for r in range(case):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	count = 0
	flag = 0
	for i in s:
		rem = (10 - int(i)) % 10
		if k - rem < 0:
			print(count)
			flag = 1
			break
		k1 = (k - rem) // 10
		val = 10 * k1 + rem
		if k >= val:
			k = val
			count += 1
		else:
			print(count)
			flag = 1
			break
	if flag == 0:
		print(len(s))


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	for i in range(n):
		x = int(s[i])
		k -= (k % 10 + x) % 10
		if k < 0:
			break
		else:
			ans += 1
	print(ans)


try:

	def binarysearch(string, K):
		X = string[::-1]
		s = 0
		p = 0
		for i in range(0, len(X)):
			if i == 0:
				item = (10 - int(X[i])) % 10
				s = s + item
			else:
				item = (10 - (s % 10 + int(X[i])) % 10) % 10
				s = s + item
		return s
	T = int(input())
	for t in range(0, T):
		(N, K) = map(int, input().split(' '))
		S = input()
		l = 0
		r = len(S) - 1
		ans = 0
		mid = 0
		while l <= r:
			mid = (l + r) // 2
			if binarysearch(S[0:mid + 1], K) <= K:
				ans = mid + 1
				l = mid + 1
			else:
				r = mid - 1
		print(ans)
except:
	pass


def check(len_tried, k, arr):
	total_felt = 0
	for j in range(len_tried - 1, -1, -1):
		num = arr[j]
		needed = (10 - (num + total_felt) % 10) % 10
		if total_felt + needed > k:
			return False
		total_felt = total_felt + needed
	return True

def solve(n, k, arr) -> int:
	l = 0
	r = n
	while r - l > 1:
		mid = (l + r) // 2
		is_possible = check(mid, k, arr)
		if is_possible:
			l = mid
		else:
			r = mid
	if check(r, k, arr):
		return r
	return l
T = int(input())
for t in range(T):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in list(input())]
	print(solve(n, k, arr))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	l = []
	c = 0
	for i in range(n):
		l.append(int(s[i]))
	ll = 0
	for i in range(n):
		if l[i] == 0:
			ll = 0
			c += 1
			continue
		if l[i] >= ll and ll != 0:
			c += 1
			ll = l[i]
			continue
		ll = l[i]
		if k - 10 >= 0 and c != 0:
			k = k - 10
			c += 1
		elif k - (10 - ll) >= 0 and c == 0:
			k = k - (10 - ll)
			c += 1
		else:
			break
	print(c)


from sys import stdin

def good_prefix(s, mid):
	operations = 0
	for i in range(mid - 1, -1, -1):
		req = (operations + int(s[i])) % 10
		if req != 0:
			operations += 10 - req
	return operations

def binary_search(s, low, high, k):
	while low < high:
		mid = low + (high - low) // 2
		op = good_prefix(s, mid)
		if op <= k:
			low = mid + 1
		else:
			high = mid
	return low - 1
t = int(stdin.readline().strip())
while t > 0:
	(n, k) = list(map(int, stdin.readline().strip().split(' ')))
	s = stdin.readline().strip()
	low = 0
	high = n + 1
	result = binary_search(s, low, high, k)
	print(result)
	t -= 1


for test in range(int(input())):
	(n, k) = map(int, input().split())
	st = input()
	low = 0
	high = n + 1
	while high - low > 1:
		mid = (high + low) // 2
		op = 0
		for i in range(mid - 1, -1, -1):
			req = (op + int(st[i])) % 10
			if req != 0:
				op = op + 10 - req
		if op <= k:
			low = mid
		elif op > k:
			high = mid
	print(low)


def zero(m, s):
	z = 0
	for i in range(m + 1):
		b = (int(s[m - i]) - int('0') + z) % 10
		if b == 0:
			continue
		z += 10 - b
	return z
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	l = 0
	r = n - 1
	m = 0
	while l <= r:
		m = l + (r - l) // 2
		if zero(m, s) > k:
			r = m - 1
		else:
			ans = m + 1
			l = m + 1
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()

	def calc_val(x):
		ans = 0
		for i in range(len(x) - 1, -1, -1):
			num = (int(x[i]) + ans) % 10
			if num != 0:
				req = 10 - num
				ans += req
		return ans
	low = 0
	high = len(s) + 1
	while high - low > 1:
		mid = (low + high) // 2
		ops = calc_val(s[:mid])
		if ops <= k:
			low = mid
		else:
			high = mid
	print(low)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	n += 1
	low = 0
	while n - low > 1:
		mid = (low + n) // 2
		operations = 0
		for i in range(mid - 1, -1, -1):
			w = (int(s[i]) + operations) % 10
			if w != 0:
				operations += 10 - w
		if operations <= k:
			low = mid
		else:
			n = mid
	print(low)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	arr = -1
	l = 0
	b = (10 - int(s[0])) % 10
	if k - b < 0:
		print(0)
		continue
	m = (k - b) // 10
	arr = b + m * 10
	l += 1
	for i in range(1, n):
		b = (10 - int(s[i])) % 10
		if arr - b < 0:
			break
		m = (arr + 10 - b) // 10
		c = b + m * 10
		if c >= 0 and c <= arr:
			arr = c
			l += 1
		else:
			m -= 1
			while m >= 0:
				c = b + m * 10
				if c >= 0 and c <= arr:
					arr = c
					l += 1
					break
				m -= 1
	print(l)


def func():
	(n, k) = map(int, input().split())
	s = input()
	l = 0
	r = n - 1
	ans = 0
	while l <= r:
		mid = (l + r) // 2
		op = 0
		for i in range(mid, -1, -1):
			value = (ord(s[i]) - ord('0') + op) % 10
			if value == 0:
				continue
			op += 10 - value
		if op <= k:
			l = mid + 1
			ans = mid + 1
		else:
			r = mid - 1
	return ans
t = int(input())
for i in range(0, t):
	print(func())


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l = 0
	r = len(s) - 1
	ans = 0

	def calc(m):
		add = 0
		for i in range(m, -1, -1):
			v = (ord(s[i]) - ord('0') + add) % 10
			if v == 0:
				continue
			add += 10 - v
		return add
	while l <= r:
		m = (l + r) // 2
		if calc(m) > k:
			r = m - 1
		else:
			ans = m + 1
			l = m + 1
	print(ans)


from sys import stdin, stdout
inp_num = lambda : int(input())
inp_lis = lambda : list(map(int, input().split()))

def cal(s, m):
	tot = 0
	for i in range(m, -1, -1):
		n = (int(s[i]) + tot) % 10
		if n == 0:
			continue
		tot = tot + (10 - n)
	return tot
for _ in range(inp_num()):
	(n, k) = map(int, input().split())
	s = input()
	an = 0
	(st, en) = (0, n - 1)
	while st <= en:
		mid = (st + en) // 2
		if cal(s, mid) > k:
			en = mid - 1
		else:
			st = mid + 1
			an = mid + 1
	print(an)


def bs(a, m, k):
	(s, p) = (0, 0)
	for i in range(m - 1, -1, -1):
		x = (a[i] + p) % 10
		y = (10 - x) % 10
		s = s + y
		p += y
	if s <= k:
		return True
	else:
		return False
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = input()
	a = [int(a[i]) for i in range(n)]
	l = 0
	h = n
	while l <= h:
		m = (l + h) // 2
		if bs(a, m, k):
			ans = m
			l = m + 1
		else:
			h = m - 1
	print(ans)


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	a = list(input())
	for i in range(len(a)):
		a[i] = int(a[i])
	h = 10 - a[0]
	g = k
	while g % 10 != h % 10 and g > 0:
		g -= 1
	c = 0
	if g <= k:
		for i in range(len(a)):
			while g % 10 != (10 - a[i]) % 10 and g > 0:
				g -= 1
			if g > 0:
				c += 1
			else:
				j = i
				while j < len(a) and a[j] == 0:
					c += 1
					j += 1
				break
	print(c)


import math
t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l = 0
	for i in range(n):
		rem = (10 - int(s[i])) % 10
		if rem > k:
			break
		l += 1
		k = (k - rem) // 10 * 10 + rem
	print(l)


from typing import List

def find_no_of_op(s: List[int], i):
	count_op = 0
	b = 0
	while i != -1:
		rem = (s[i] + b) % 10
		a = (10 - rem) % 10
		count_op += a
		b += a
		i -= 1
	return count_op

def linear_search(A: list, k: int) -> int:
	n = len(A)
	ans = n
	for i in range(0, n):
		n_op = find_no_of_op(A, i)
		if n_op > k:
			ans = i
			break
	return ans

def binary_search(A: list, k: int) -> int:
	n = len(A)
	low = 0
	high = n
	if find_no_of_op(A, low) > k:
		return 0
	while high - low != 1:
		mid = (low + high) // 2
		if find_no_of_op(A, mid) <= k:
			low = mid
		else:
			high = mid
	return high
test_cases = int(input())
for _ in range(test_cases):
	(n, k) = list(map(int, input().split()))
	s = input()
	l = [int(c) for c in s]
	ans = binary_search(l, k)
	print(ans)


import re

def func(n, k, s):
	low = 0
	high = n + 1
	while high - low > 1:
		mid = (high + low) // 2
		ops = 0
		for i in range(mid - 1, -1, -1):
			req = (ops + int(s[i])) % 10
			if req != 0:
				ops += 10 - req
		if ops <= k:
			low = mid
		else:
			high = mid
	return low
t = int(input())
ans = []
for i in range(t):
	li = [int(x) for x in input().split()]
	(n, k) = (li[0], li[1])
	s = input()
	ans.append(func(n, k, s))
for i in ans:
	print(i)


t = int(input())

def can_zero_upto_index_m(a, m, k):
	num_ops_on_prev_elements = 0
	for i in range(m, -1, -1):
		x = a[i]
		x += num_ops_on_prev_elements
		x %= 10
		if x == 0:
			continue
		if k >= 10 - x:
			k -= 10 - x
			num_ops_on_prev_elements += 10 - x
		else:
			return False
	return True
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input()]
	(i, j, ans) = (0, n - 1, -1)
	while i <= j:
		m = (i + j) // 2
		if can_zero_upto_index_m(a, m, k):
			ans = m
			i = m + 1
		else:
			j = m - 1
	ans += 1
	print(ans)


try:
	for _ in range(int(input())):
		(n, k) = list(map(int, input().split()))
		s = input()
		low = 0
		high = n + 1
		while high - low > 1:
			mid = (high + low) // 2
			ops = 0
			for i in range(mid - 1, -1, -1):
				req = (ops + int(s[i])) % 10
				if req != 0:
					ops += 10 - req
			if ops <= k:
				low = mid
			else:
				high = mid
		print(low)
except:
	pass


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

	def check(m, s):
		add = 0
		for i in range(m, -1, -1):
			r = (int(s[i]) + add) % 10
			if r == 0:
				continue
			add += 10 - r
		return add
	(l, r) = (0, n - 1)
	ans = 0
	while l <= r:
		m = l + (r - l) // 2
		if check(m, s) <= k:
			ans = m + 1
			l = m + 1
		else:
			r = m - 1
	print(ans)


def possible(S, ind, K):
	total = 0
	for i in reversed(range(ind)):
		req = (10 - int(S[i])) % 10
		total += (10 + req - total % 10) % 10
		if total > K:
			return False
	return True
for _ in range(int(input())):
	(N, K) = map(int, input().strip().split())
	S = input().strip()
	(low, high) = (0, N)
	ans = 0
	while low <= high:
		mid = (low + high) // 2
		if possible(S, mid, K):
			ans = mid
			low = mid + 1
		else:
			high = mid - 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	res = 0
	for i in range(n):
		req = (10 - (ord(s[i]) - ord('0'))) % 10
		if req > k:
			break
		res += 1
		k = (k - req) // 10 * 10 + req
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	low = 0
	high = n + 1
	while high - low > 1:
		mid = (low + high) // 2
		ops = 0
		for i in range(mid - 1, -1, -1):
			ops += (10 - (int(s[i]) + ops) % 10) % 10
		if ops <= k:
			low = mid
		else:
			high = mid
	print(low)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l = 0
	u = n - 1
	ans = 0
	while l <= u:
		mid = (u + l) // 2
		add = 0
		for i in range(mid, -1, -1):
			v = (ord(s[i]) - ord('0') + add) % 10
			if v == 0:
				continue
			add = 10 - v + add
		if add > k:
			u = mid - 1
		else:
			l = mid + 1
			ans = mid + 1
	print(ans)


def prefx(s, r):
	ops = 0
	for i in range(r - 1, -1, -1):
		req = (ops + ord(s[i]) - ord('0')) % 10
		if req != 0:
			ops += 10 - req
	return ops
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l = 0
	r = n + 1
	while r - l > 1:
		mid = (l + r) // 2
		if prefx(s, mid) <= k:
			l = mid
		else:
			r = mid
	print(l)


cas = int(input())
while cas != 0:
	cas -= 1
	(n, kk) = map(int, input().split())
	s = input()
	l = 0
	r = n + 1
	while r - l > 1:
		mid = (l + r) // 2
		ops = 0
		for i in range(mid - 1, -1, -1):
			req = (ops + int(s[i])) % 10
			if req:
				ops += 10 - req
		if ops <= kk:
			l = mid
		else:
			r = mid
	print(l)


from xml.dom import minidom

def tInt():
	n = int(input())
	return n

def tList():
	a = map(int, input().split())
	return a

def tStr():
	s = input()
	return s

def isPos(s, l, k):
	total = 0
	for i in range(l - 1, -1, -1):
		temp = int(s[i]) + total
		temp %= 10
		if temp != 0:
			temp = 10 - temp
		else:
			temp = 0
		total += temp
		if total > k:
			return False
	return True

def solve():
	for _ in range(tInt()):
		(m, k) = tList()
		s = tStr()
		left = 1
		right = m
		ans = 0
		while left <= right:
			mid = (left + right) // 2
			if isPos(s, mid, k) == True:
				ans = mid
				left = mid + 1
			else:
				right = mid - 1
		print(ans)
solve()


def find(a):
	return (10 - a) % 10
for t in range(int(input())):
	(N, K) = map(int, input().split())
	S = str(input())
	ans = 0
	for i in range(N):
		temp = find(int(S[i]))
		if temp > K:
			break
		ans += 1
		K = temp + 10 * ((K - temp) // 10)
	print(ans)


def find(a):
	return (10 - a) % 10

def BS(x, S, K):
	shift = 0
	for i in range(x, -1, -1):
		v = int(S[i])
		v += shift
		v %= 10
		curr = find(v)
		shift += curr
	return shift <= K
for t in range(int(input())):
	(N, K) = map(int, input().split())
	S = str(input())
	if not BS(0, S, K):
		print(0)
		continue
	l = 0
	r = int(N - 1)
	while r - l > 1:
		mid = (l + r) // 2
		if BS(mid, S, K):
			l = mid
		else:
			r = mid - 1
	if BS(r, S, K):
		print(r + 1)
	else:
		print(l + 1)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	l = list(map(int, list(input())))
	(low, high) = (0, n + 1)
	f = 0
	ma = 0
	while low < high:
		mid = low + (high - low) // 2
		new = k
		gy = 0
		for j in range(mid - 1, -1, -1):
			x = (l[j] + gy) % 10
			if x % 10 != 0:
				new = new - (10 - x % 10)
				gy = gy + 10 - x % 10
		if new >= 0:
			low = mid + 1
			ma = mid
		else:
			high = mid
	print(ma)
	t -= 1


def getop(s):
	l = len(s)
	curr = 0
	idx = l - 1
	while idx >= 0:
		req = abs(curr + s[idx]) % 10
		curr = curr + (10 - req) % 10
		idx -= 1
	return curr

def func():
	(n, k) = map(int, input().split())
	l = [int(i) for i in input()]
	low = 0
	high = n - 1
	mx = 0
	while high >= low:
		mid = (low + high) // 2
		curr = getop(l[:mid + 1])
		if curr > k:
			high = mid - 1
		else:
			low = mid + 1
			mx = max(mx, mid + 1)
	print(mx)
t = int(input())
for i in range(t):
	func()


from math import ceil
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input()))
	ss = [0]
	cnt = 1
	for i in range(1, n):
		if arr[i - 1] <= arr[i]:
			cnt += 1
		else:
			ss.append(ss[-1] + cnt)
			cnt = 1
	ss.append(n)
	(ind, off) = (0, 0)
	l = len(ss)
	for i in range(l - 1):
		if any((el != 0 for el in arr[ss[i]:ss[i + 1]])):
			if i == 0 and k >= 10 - arr[0]:
				k -= 10 - arr[0]
			elif i != 0 and k >= 10:
				k -= 10
			else:
				for k in range(ss[i], ss[i + 1]):
					if arr[k] == 0:
						off += 1
					else:
						break
				break
		ind += 1
	print(ss[ind] + off)


def solve(n, k, li):
	ans = 0
	lo = 0
	hi = n - 1

	def check(mid):
		opr = 0
		last = prev = li[mid]
		oldval = 0
		for i in range(mid, -1, -1):
			if (li[i] + oldval) % 10 <= prev:
				prev = (li[i] + oldval) % 10
			else:
				if prev != 0:
					val = 10 - prev
				elif last == 0:
					val = 0
				else:
					val = 10
				opr += val
				oldval = (oldval + val) % 10
				last = prev = (li[i] + oldval) % 10
		if prev != 0:
			val = 10 - prev
		elif last == 0:
			val = 0
		else:
			val = 10
		opr += val
		return opr
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if check(mid) <= k:
			ans = mid + 1
			lo = mid + 1
		else:
			hi = mid - 1
	return ans
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, list(input())))
	print(solve(n, k, s))


def chkFunction(ind, st):
	prev = 0
	for x in range(ind, -1, -1):
		new = prev + int(st[x])
		if new % 10 != 0:
			prev += 10 - new % 10
	return prev
for tc in range(int(input())):
	ls = list(map(int, input().split()))
	(n, k) = (ls[0], ls[1])
	s = input()
	ans = -1
	lo = 0
	hi = len(s) - 1
	hope = 0
	while lo <= hi:
		mid = (lo + hi) // 2
		if chkFunction(mid, s) <= k:
			ans = mid
			lo = mid + 1
		else:
			hi = mid - 1
	print(ans + 1)


def check(index, s):
	temp = 0
	ans = 0
	for i in range(index - 1, -1, -1):
		val = int(s[i])
		val = (val + temp) % 10
		temp += (10 - val) % 10
	return temp
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	low = 0
	high = n
	while low <= high:
		mid = (low + high) // 2
		val = check(mid, s)
		if val > k:
			high = mid - 1
		elif val <= k:
			res = mid
			low = mid + 1
	print(res)


N = int(input())
for _ in range(N):
	(n, k) = map(int, input().split())
	s = input()
	hi = n
	lo = 0
	ans = 0
	while lo <= hi:
		mid = (lo + hi) // 2
		ops = 0
		for i in range(mid - 1, -1, -1):
			req = (ops + int(s[i])) % 10
			if req != 0:
				ops += 10 - req
		if ops <= k:
			ans = mid
			lo = mid + 1
		else:
			hi = mid - 1
	print(ans)


from copy import deepcopy

def run(k, s):
	max_ops = [k]
	i = 1
	while i <= len(s):
		curr_arr_i = i - 1
		curr_min_ops = (10 - s[curr_arr_i]) % 10
		ops_avail = max_ops[i - 1]
		if curr_min_ops > ops_avail:
			break
		n_times = (ops_avail - curr_min_ops) // 10
		max_ops.append(curr_min_ops + n_times * 10)
		i += 1
	return i - 1
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(map(int, input()))
	print(run(k, s))


import sys, os, io
input = sys.stdin.readline
from collections import defaultdict
import bisect
import random
PI = 3.141592653589793
INF = float('inf')
MOD = 1000000007

def bin32(num):
	return '{0:032b}'.format(num)

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

def ii():
	return int(input())

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]
for t in range(ii()):
	t += 1
	(n, k) = li()
	s = input().strip()
	s = [int(i) for i in s]
	r = (10 - s[0]) % 10
	while k >= 0 and k % 10 != r:
		k -= 1
	ans = 1
	if k < 0:
		ans = 0
	for i in range(1, n):
		if k < 0:
			break
		r = (10 - s[i]) % 10
		diff = k % 10 - r
		if diff < 0:
			k = k // 10 * 10
			k -= s[i]
			if k < 0:
				break
			ans += 1
			continue
		if k < diff:
			break
		ans += 1
		k -= diff
	print(ans)


n = int(input())

def ans(s, k):
	import math
	z = k
	for i in range(len(s)):
		x = 10 - int(s[i])
		z -= x
		ans = math.floor(z / 10)
		x += 10 * ans
		z = x
		if z < 0:
			return i
	return len(s)
for _ in range(n):
	arr = [int(i) for i in input().split()]
	s = input()
	print(ans(s, arr[1]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input()))
	l = 0
	h = n + 1
	while h - l > 1:
		m = (l + h) // 2
		o = 0
		for i in reversed(range(m)):
			r = (o + s[i]) % 10
			if r != 0:
				o += 10 - r
		if o <= k:
			l = m
		else:
			h = m
	print(l)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = input()
	s = list(map(lambda x: int(x), s))
	x = 0
	count = 0
	(l, h) = (0, a - 1)
	while l <= h:
		mid = (l + h) // 2
		x = 0
		for j in range(mid, -1, -1):
			r = (s[j] + x) % 10
			if r != 0:
				x += 10 - r
			if b < x:
				break
			if j == 0:
				count = max(count, mid + 1)
		if b < x:
			h = mid - 1
		else:
			l = mid + 1
	print(count)


def valid(m, s):
	temp = 0
	for i in range(m, -1, -1):
		v = (int(s[i]) + temp) % 10
		if v == 0:
			continue
		temp += 10 - v
	return temp
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, list(input())))
	low = 0
	high = n - 1
	ans = 0
	while low <= high:
		mid = (low + high) // 2
		if valid(mid, arr) > k:
			high = mid - 1
		else:
			low = mid + 1
			ans = mid + 1
	print(ans)


x = int(input())
for i in range(x):
	(n, k) = list(map(int, input().split()))
	z = input()
	ans = 0
	jj = 0
	p = 0
	while jj < n:
		if z[jj] == '0':
			p += 1
		else:
			break
		jj += 1
	if jj < n:
		flag = 0
		if jj == 0 and ans + 10 - int(z[jj]) <= k:
			ans += 10 - int(z[jj])
			p += 1
			final = int(z[jj])
			jj += 1
			flag = 1
		elif ans + 10 <= k:
			ans += 10
			p += 1
			final = int(z[jj])
			jj += 1
			flag = 1
		if flag == 1:
			for kk in range(jj, n):
				if z[kk] != '0' and (int(z[kk]) < int(z[kk - 1]) or z[kk - 1] == '0'):
					final = int(z[kk])
					if ans + 10 <= k:
						ans += 10
						p += 1
					else:
						break
				else:
					if z[kk] != '0':
						final = int(z[kk])
					p += 1
	print(p)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input().split())[0]
	ls = [int(i) for i in s]
	l = 0
	h = n + 1
	final = 0
	while l < h:
		m = l + h >> 1
		tem = ls[:m]
		add = 0
		new = 0
		for i in range(m - 1, -1, -1):
			tem[i] = (tem[i] + add) % 10
			if tem[i] == 0:
				continue
			else:
				add = 10 - tem[i]
				new += add
				tem[i] = 0
				add = new
		if new <= k:
			l = m + 1
			final = len(tem)
		elif new > k:
			h = m
	print(final)


def compute(s):
	net = 0
	for i in s[::-1]:
		x = (int(i) + net) % 10
		if x == 0:
			continue
		net += 10 - x
	return net
t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	(low, high) = (1, n)
	while low <= high:
		mid = (low + high) // 2
		if compute(s[:mid]) > k:
			high = mid - 1
		else:
			ans = mid
			low = mid + 1
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	s = input()
	A = []
	for j in range(n):
		if int(s[j]) != 0:
			A.append(10 - int(s[j]))
		else:
			A.append(0)
	flag = A[0]
	if flag > k:
		print(0)
		continue
	for j in range(n - 1):
		if A[j] < A[j + 1]:
			flag += 10
		if flag > k:
			print(j + 1)
			break
	if flag <= k:
		print(n)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		(n, k) = sep()
		s = inp()
		lo = 0
		hi = n
		ans = 0
		s = list(s)
		while lo <= hi:
			mid = (lo + hi) // 2
			res = 0
			for i in range(mid - 1, -1, -1):
				cnt = (10 - (int(s[i]) + res) % 10) % 10
				res += cnt
			if res <= k:
				lo = mid + 1
				ans = mid
			else:
				hi = mid - 1
		print(ans)
main()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	limit = 0
	n = n + 1
	while n - limit > 1:
		mid = (limit + n) // 2
		operation = 0
		i = mid - 1
		while i >= 0:
			w = (int(s[i]) + operation) % 10
			if w != 0:
				operation = operation + (10 - w)
			i = i - 1
		if operation <= k:
			limit = mid
		else:
			n = mid
	print(limit)


import sys

def readInt():
	x = int(sys.stdin.readline().rstrip())
	return x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x
write = sys.stdout.write
read = sys.stdin.readline

def solve():
	(n, k) = readList()
	s = read().rstrip('\n')
	ops = 0
	ans = -1
	lo = 0
	hi = n - 1
	while lo <= hi:
		mid = (lo + hi) // 2
		ops = 0
		for i in range(mid, -1, -1):
			a = (int(s[i]) + ops) % 10
			if a > 0:
				ops += 10 - a
		if ops <= k:
			ans = max(lo, ans)
			lo = mid + 1
		else:
			hi = mid - 1
	print(lo)

def main():
	t = 1
	t = readInt()
	for _ in range(t):
		solve()
main()


import math
iter = int(input())
for z in range(iter):
	(n, k) = list(map(int, input().split(' ')))
	arr = input()
	depth = 0
	for i in range(n):
		mul = math.floor((k - (10 - int(arr[i])) % 10) / 10)
		if mul >= 0:
			k = (10 - int(arr[i])) % 10 + 10 * mul
		else:
			break
		depth += 1
	print(depth)


t = int(input())
for i in range(0, t):
	s = [int(i) for i in input().split()]
	(n, k) = (s[0], s[1])
	l = list(input())
	for i in range(0, n):
		l[i] = int(l[i])
	c = 0
	for p in range(0, n):
		f = 0
		for i in range(k, -1, -1):
			if (l[p] + i) % 10 == 0:
				x = i
				f = 1
				break
		if f == 1:
			c = c + 1
		else:
			print(c)
			break
		k = x
		if p == n - 1:
			print(c)
			break


from bisect import bisect

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = list(map(int, input()))
		a = [(10 - x) % 10 for x in s]
		b = a[:]
		for i in range(1, len(a)):
			if a[i - 1] >= a[i]:
				b[i] = b[i - 1]
			else:
				b[i] = b[i - 1] + 10
		print(bisect(b, k))
main()


def AbhiSolveKiya(s, N, k):
	s = list(map(int, list(s)))
	n = len(s)
	if s[0] > 0 and k < 10 - s[0]:
		return 0
	low = 0
	high = n - 1
	best = -1
	while low <= high:
		n = (low + high) // 2
		pre = [0] * (n + 1)
		total = 0
		for i in range(n, -1, -1):
			x = (s[i] + total) % 10
			if x == 0:
				x = 10
			pre[i] = 10 - x
			total += 10 - x
			total %= 10
			if i < n:
				pre[i] += pre[i + 1]
		if pre[0] <= k:
			low = n + 1
			best = max(n, best)
		else:
			high = n - 1
	return best + 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(AbhiSolveKiya(s, n, k))


from sys import stdin, stdout

def main():
	t = int(stdin.readline())
	for tt in range(t):
		(n, k) = map(int, stdin.readline().split())
		s = list(map(int, list(stdin.readline().strip())))
		if k < 10 - s[0] and s[0] != 0:
			print(0)
		else:
			db = 1
			if s[0] != 0:
				k = k - (10 - s[0])
			for i in range(1, n):
				if s[i] == 0:
					db += 1
				elif s[i] >= s[i - 1] and s[i - 1] != 0:
					db += 1
				else:
					if k >= 10:
						db += 1
					k -= 10
				if k < 0:
					break
			print(db)
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = []
	b = []
	a.append((10 - int(s[0])) % 10)
	b.append((10 - int(s[0])) % 10)
	if a[0] > k:
		print(0)
	else:
		f = 0
		for i in range(1, n):
			x = (10 - int(s[i])) % 10
			b.append(x)
			if b[i - 1] < x:
				a.append(10 + a[i - 1])
			else:
				a.append(a[i - 1])
			if a[i] > k:
				f = i
				break
		if f != 0:
			print(f)
		else:
			print(n)


t = int(input())

def solve(s, m):
	x = 0
	for i in range(m, -1, -1):
		v = (int(s[i]) + x) % 10
		if v == 0:
			continue
		x += 10 - v
	return x

def bsrch(s, n, k):
	(l, r) = (0, n - 1)
	while l <= r:
		m = (l + r) // 2
		if solve(s, m) > k:
			r = m - 1
		else:
			l = m + 1
	return l
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	print(bsrch(s, n, k))


try:
	for tc in range(int(input())):
		(n, k) = list(map(int, input().split()))
		st = input()
		cnt = 0
		for i in range(n):
			curr = 10 - int(st[i]) % 10
			now = k // 10
			to = 10 * now + curr
			if to > k:
				to -= 10
			if to <= k and to >= 0:
				cnt += 1
				k = to
			else:
				break
		print(cnt)
except:
	pass