Read problems statements in [Russian] and [Bengali].

There's a zebra crossing appearing in the middle of nowhere with N blocks in it. The colors of the zebra crossing is represented by a binary string S, where S_{i} is 1 if the i-th block from the left is white, and 0 if the block is black.

Chef really wants to play with the zebra crossing. Although the given zebra crossing might not have alternate black and white blocks, Chef wants to follow the alternating white-black color pattern while crossing it.

Initially, Chef stands at block 1. Chef has to jump exactly K times, and in each jump he has to move forward and jump to a different color than that previously occupied by Chef. More formally, suppose that Chef is currently at block i and wants to jump to block j then following conditions should hold:

i < j
S_{i} \neq S_{j}

Output the farthest block Chef can reach with exactly K jumps. If Chef cannot jump exactly K times, output -1.

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

- The first line 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 integers N and K.
- The second line of each test case consists of a binary string of length N denoting the color of blocks of the zebra crossing.

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

For each test case, output the farthest block Chef can reach with exactly K jumps, or -1 in case Chef cannot jump exactly K times.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{3}$
$1 ≤ K ≤ N$
- Sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
6 2
100101
5 1
10111
6 1
000000

----- Sample Output 1 ------ 
6
2
-1

----- explanation 1 ------ 
- For the first test case, Chef can jump in the following order: $1 \rightarrow 5 \rightarrow 6$.

- For the second test case, Chef can jump in the following order: $1 \rightarrow 2$.

- For the third test case, Chef cannot make any jumps.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
d = {'1': '0', '0': '1'}
for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	if k % 2:
		f = d[s[0]]
	else:
		f = s[0]
	p = s[0]
	for i in s:
		if i != p:
			k -= 1
			p = d[p]
			if k == 0:
				break
	if k:
		print(-1)
	else:
		for i in range(n):
			if s[-1 - i] == f:
				break
		print(n - i)


def soln(n, k, s):
	cond = ''
	inds = []
	i = 0
	while i < n:
		cur = s[i]
		cond += s[i]
		while i < n and s[i] == cur:
			i += 1
		inds.append(i)
	if k >= len(cond):
		return -1
	if cond[0] == cond[-1]:
		if k & 1:
			return inds[-2]
		else:
			return inds[-1]
	elif k & 1:
		return inds[-1]
	else:
		return inds[-2]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(soln(n, k, s))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	one_zero = s.count('10')
	zero_one = s.count('01')
	if k > one_zero + zero_one:
		print('-1')
		continue
	start = s[0]
	if k % 2 == 0:
		i = n - 1
		while True:
			if s[i] == start:
				print(i + 1)
				break
			i -= 1
	else:
		i = n - 1
		while True:
			if s[i] != start:
				print(i + 1)
				break
			i -= 1


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	S = input()
	s = S[0]
	x = 0
	for i in range(1, N):
		if S[i] != S[i - 1]:
			x += 1
	if K > x:
		print(-1)
		continue
	S = S[::-1]
	if K % 2 == 0:
		print(N - S.index(s))
	else:
		print(N - S.index(str(int(not bool(int(s))))))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ali = [int(a) for a in input()]
	fs = ali[0]
	ck = k
	cn = fs
	for a in ali:
		if a != cn:
			cn = a
			ck -= 1
	if ck > 0:
		print(-1)
	else:
		ali.reverse()
		zs = 0
		ons = 0
		hon = False
		hz = False
		if ali.__contains__(0):
			hz = True
			zs = n - ali.index(0)
		if ali.__contains__(1):
			hon = True
			ons = n - ali.index(1)
		ans = 0
		if fs == 0 and k % 2 == 1:
			ans = ons
		elif fs == 1 and k % 2 == 0:
			ans = ons
		elif fs == 1 and k % 2 == 1:
			ans = zs
		elif fs == 0 and k % 2 == 0:
			ans = zs
		if hon and hz:
			print(ans)
		else:
			print(-1)


def solve():
	(last_zero, last_one) = (path.rfind('0') + 1, path.rfind('1') + 1)
	new_path = path[0]
	count = 0
	for i in range(1, n):
		if path[i] != new_path:
			new_path = path[i]
			count += 1
	if count >= k:
		if path[0] == '1':
			if k % 2 == 1:
				print(last_zero)
			else:
				print(last_one)
		elif k % 2 == 1:
			print(last_one)
		else:
			print(last_zero)
	else:
		print(-1)
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	path = input()
	solve()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = input()
	c = 0
	for j in range(1, n):
		if l[j] != l[j - 1]:
			c += 1
	if c < k:
		print('-1')
		continue
	if l[0] == '1':
		if k % 2 == 0:
			print(l.rfind('1') + 1)
		else:
			print(l.rfind('0') + 1)
	elif k % 2 != 0:
		print(l.rfind('1') + 1)
	else:
		print(l.rfind('0') + 1)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	for _ in tr():
		(n, k) = sm()
		zebra = line()
		count = 0
		for i in range(n - 1):
			if zebra[i] != zebra[i + 1]:
				count += 1
		if count < k:
			print(-1)
		else:
			position = 1
			if k & 1:
				if zebra[0] == '1':
					position += zebra.rindex('0')
				else:
					position += zebra.rindex('1')
			elif zebra[0] == '1':
				position += zebra.rindex('1')
			else:
				position += zebra.rindex('0')
			print(position)
main()


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


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	s = input()
	ct = 0
	x = s[0]
	y = 0
	z = 0
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			z = i + 1
			break
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			y = i + 1
			break
	for i in range(1, n):
		if x == '0' and s[i] == '1':
			ct += 1
			x = s[i]
		elif x == '1' and s[i] == '0':
			ct += 1
			x = s[i]
	if s[0] == '0':
		for i in range(k):
			if i % 2 == 0:
				x = '1'
			else:
				x = '0'
	elif s[0] == '1':
		for i in range(k):
			if i % 2 == 0:
				x = '0'
			else:
				x = '1'
	if ct >= k:
		if x == '0':
			print(y)
		else:
			print(z)
	else:
		print(-1)


tc = int(input())
for j in range(tc):
	ip = list(map(int, input().rstrip().split()))
	n = ip[0]
	k = ip[1]
	s = input()
	ar = []
	loo = 0
	lzo = 0
	for i in range(n):
		ar.append(int(s[i]))
		if int(s[i]) == 1:
			loo = i
		if int(s[i]) == 0:
			lzo = i
	loo += 1
	lzo += 1
	br = []
	br.append(ar[0])
	for i in range(1, n):
		if ar[i] != ar[i - 1]:
			br.append(ar[i])
	gg = len(br)
	if gg == 1:
		print(-1)
		continue
	if k > gg - 1:
		print(-1)
		continue
	if br[0] == 1:
		if k % 2 == 1:
			print(lzo)
		if k % 2 == 0:
			print(loo)
	if br[0] == 0:
		if k % 2 == 1:
			print(loo)
		if k % 2 == 0:
			print(lzo)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			c += 1
	if c < k:
		print('-1')
		continue
	if s[0] == '1':
		if k % 2 == 0:
			print(s.rfind('1') + 1)
		else:
			print(s.rfind('0') + 1)
	elif k % 2 != 0:
		print(s.rfind('1') + 1)
	else:
		print(s.rfind('0') + 1)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s_rev = s[::-1]
	start = s[0]
	if s.count('01') + s.count('10') >= k:
		if k % 2 == 0:
			for i in s_rev:
				if i == start:
					print(n - s_rev.index(i))
					break
		else:
			for i in s_rev:
				if i != start:
					print(n - s_rev.index(i))
					break
	else:
		print('-1')


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	pos = 0
	next_pos = 1
	while next_pos < n and k > 1:
		if s[next_pos] != s[pos]:
			pos = next_pos
			k -= 1
		next_pos += 1
	if k == 1:
		for i in range(n - 1, pos, -1):
			if s[i] != s[pos]:
				k -= 1
				pos = i
				break
	if k == 0:
		print(pos + 1)
	else:
		print(-1)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	pos = 0
	next_pos = 1
	while next_pos < n and k > 1:
		if s[next_pos] != s[pos]:
			pos = next_pos
			k -= 1
		next_pos += 1
	if k == 1:
		for i in range(n - 1, pos, -1):
			if s[i] != s[pos]:
				k -= 1
				pos = i
				break
	if k == 0:
		print(pos + 1)
	else:
		print(-1)


def main():
	tc = int(input())
	while tc > 0:
		i = input().split()
		n = int(i[0])
		k = int(i[1])
		s = input()
		alt = 0
		for i in range(1, n):
			if s[i] != s[i - 1]:
				alt += 1
		if alt < k:
			print(-1)
		else:
			for i in range(n - 1, -1, -1):
				if k % 2 == 0 and s[i] == s[0]:
					print(i + 1)
					break
				elif k % 2 != 0 and s[i] != s[0]:
					print(i + 1)
					break
		tc -= 1
main()


def func2(str1, k):
	i = 0
	rstr = ''
	while i < len(str1) - 1:
		if str1[i] != str1[i + 1]:
			rstr += str1[i]
		i += 1
	rstr += str1[-1]
	if len(rstr) == 1:
		print(-1)
		return
	if k > len(rstr) - 1:
		print(-1)
		return
	if k % 2 == 0:
		if len(rstr) % 2 == 1:
			print(len(str1))
			return
		else:
			req = rstr[len(rstr) - 2]
			for i in range(len(str1) - 1, -1, -1):
				if str1[i] == req:
					print(i + 1)
					return
	elif len(rstr) % 2 == 0:
		print(len(str1))
		return
	else:
		req = rstr[len(rstr) - 2]
		for i in range(len(str1) - 1, -1, -1):
			if str1[i] == req:
				print(i + 1)
				return
t = int(input())
for i in range(t):
	l1 = [int(i) for i in input().split()]
	s = input()
	func2(s, l1[1])


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	a = list(input())
	if a[len(a) - 1] == '\r':
		a.pop()
	c1 = 0
	d = []
	x = a[0]
	for i in range(len(a)):
		if a[i] != x:
			x = a[i]
			c1 += 1
		d.append(c1)
	c2 = 0
	for i in range(len(a) - 1, 0, -1):
		if k % 2 == 0 and a[i] == a[0]:
			if d[i] >= k:
				print(i + 1)
				c2 += 1
				break
		elif k % 2 and a[i] != a[0]:
			if d[i] >= k:
				print(i + 1)
				c2 += 1
				break
	if c2 == 0:
		print(-1)


for x in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input()))
	i = 0
	j = 0
	maxIndex = -1
	while j < n:
		if k > 1:
			if s[j] != s[i]:
				k -= 1
				i = j
		elif s[j] != s[i]:
			maxIndex = j
		j += 1
	print(maxIndex + 1 if maxIndex != -1 else -1)


import collections
import math

def nice(n, k, s):
	firstLetter = s[0]
	maxJumps = 0
	lastIndex = -1
	if not k % 2:
		lastIndex = s.rindex(firstLetter)
	elif str(int(firstLetter) ^ 1) in s:
		lastIndex = s.rindex(str(int(firstLetter) ^ 1))
	for i in range(1, lastIndex):
		if s[i] != s[i - 1]:
			maxJumps += 1
	if k - 1 <= maxJumps and lastIndex != -1:
		return lastIndex + 1
	return -1
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(nice(n, k, s))


def func(arr, k):
	jpos = 0
	for i in range(0, len(arr) - 1):
		if arr[i] != arr[i + 1]:
			jpos += 1
	if k <= jpos:
		if k % 2 == 0:
			end = arr[0]
		elif arr[0] == '0':
			end = '1'
		else:
			end = '0'
	else:
		return -1
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] == end:
			return i + 1
t = int(input())
for i in range(0, t):
	(n, k) = list(map(int, input().strip().split()))
	arr = input()
	print(func(arr, k))


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	zebra = input()
	previous = zebra[0]
	steps = 1
	for j in range(len(zebra)):
		if K == 0:
			break
		if zebra[j] != previous and K != 1:
			if j == len(zebra) - 1:
				steps = j + 1
				previous = zebra[j]
				K -= 1
			else:
				steps = j + 1
				previous = zebra[j]
				K -= 1
		elif zebra[j] != previous and K == 1:
			if j == len(zebra) - 1:
				steps = j + 1
				previous = zebra[j]
				K -= 1
			elif zebra[j] not in zebra[j + 1:]:
				steps = j + 1
				previous = zebra[j]
				K -= 1
		else:
			pass
	if K != 0:
		print(-1)
	else:
		print(steps)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			c += 1
	if c < k:
		print(-1)
	elif k % 2 == 0:
		x = s[0]
		for i in range(n - 1, -1, -1):
			if s[i] == x:
				print(i + 1)
				break
	else:
		x = int(s[0])
		x = str(abs(x - 1))
		for i in range(n - 1, -1, -1):
			if s[i] == x:
				print(i + 1)
				break


try:
	T = int(input())
	for t in range(T):
		(N, K) = tuple(input().split())
		(N, K) = (int(N), int(K))
		s = str(input())
		x = 0
		count = 0
		for i in range(N - 1):
			if s[i] != s[i + 1]:
				count += 1
		if count >= K:
			if K % 2 == 0:
				for i in range(N - 1, 0, -1):
					if s[i] == s[0]:
						x = i + 1
						break
			else:
				for i in range(N - 1, 0, -1):
					if s[i] != s[0]:
						x = i + 1
						break
			print(x)
		else:
			print(-1)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s += 'a'
	s1 = []
	l = 0
	for i in range(n):
		if s[i] != s[i + 1]:
			s1.append(i + 1)
			l += 1
	if l - 1 < k:
		print(-1)
	elif (l - 1) % 2 == 0:
		if k % 2 == 0:
			print(s1[-1])
		else:
			print(s1[-2])
	elif k % 2 == 0:
		print(s1[-2])
	else:
		print(s1[-1])


tt = int(input())
for i in range(tt):
	(n, k) = [int(_) for _ in input().split()]
	s = input()
	stCh = s[0]
	if stCh == '0':
		nCh = '1'
	else:
		nCh = '0'
	if k % 2 == 0:
		lstPos = n - s[::-1].find(stCh)
	else:
		lstPos = n - s[::-1].find(nCh)
	if s.count(nCh) > 0:
		if lstPos <= n:
			st = 1
			f = False
			for ii in range(k):
				prevSt = st
				st += s[st:].find(nCh) + 1
				if st == prevSt:
					f = True
					break
				if nCh == '0':
					nCh = '1'
				else:
					nCh = '0'
			if ii != k - 1 or f:
				print(-1)
			else:
				print(lstPos)
	else:
		print('-1')


T = int(input())
for t in range(T):
	(N, K) = list(map(int, input().split()))
	B = input().split()[0]
	current_index = 0
	possible_K = 0
	for i in range(N - 1):
		if B[i] != B[i + 1]:
			possible_K += 1
	if possible_K >= K:
		for k in range(K):
			for n in range(N):
				index_to_go = -(n + 1)
				if B[index_to_go] != B[current_index]:
					current_index = N + index_to_go
					break
	if current_index == 0 or possible_K < K:
		print('-1')
	else:
		print(current_index + 1)


t = int(input())

def funcCheck(arr):
	ct = 0
	flag = arr[0]
	for i in arr:
		if flag != i:
			ct += 1
			flag = i
	return ct
for i in range(t):
	(n, k) = list(map(int, input().strip().split()))
	arr = input()
	if funcCheck(arr) < k:
		print('-1')
		continue
	ans = 0
	if arr[0] == '0':
		if k % 2 == 0:
			for i in range(len(arr) - 1, -1, -1):
				if arr[i] == '0':
					ans = i + 1
					break
		else:
			for i in range(len(arr) - 1, -1, -1):
				if arr[i] == '1':
					ans = i + 1
					break
	elif k % 2 == 0:
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] == '1':
				ans = i + 1
				break
	else:
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] == '0':
				ans = i + 1
				break
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(input())
	start = a[0]
	end = ''
	if k % 2 == 0:
		if start == '1':
			end = '1'
		else:
			end = '0'
	elif start == '1':
		end = '0'
	else:
		end = '1'
	for i in range(len(a) - 1, -1, -1):
		if a[i] == end:
			break
	ans = i
	cur = end
	c = 0
	for j in range(i - 1, -1, -1):
		if a[j] != cur:
			cur = a[j]
			c += 1
	if c >= k:
		print(ans + 1)
	else:
		print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	if k % 2 == 0:
		eo = 0
	else:
		eo = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			count += 1
	if count < k:
		print(-1)
		continue
	else:
		for i in range(n - 1, -1, -1):
			if not eo and s[0] == s[i]:
				print(i + 1)
				break
			elif eo and s[0] != s[i]:
				print(i + 1)
				break


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			count += 1
	if count < k:
		print(-1)
	elif k % 2 == 0:
		if s[0] == '1':
			print(s.rfind('1') + 1)
		else:
			print(s.rfind('0') + 1)
	elif s[0] == '1':
		print(s.rfind('0') + 1)
	else:
		print(s.rfind('1') + 1)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = input()
	c = 0
	for j in range(n - 1):
		if l[j] != l[j + 1]:
			c = c + 1
	if c < k:
		print(-1)
	elif k % 2 != 0 and l[n - 1] == l[0]:
		for j in range(n - 1, -1, -1):
			if l[j] != l[0]:
				print(j + 1)
				break
	elif k % 2 != 0 and l[n - 1] != l[0]:
		for j in range(n - 1, -1, -1):
			if l[j] != l[0]:
				print(j + 1)
				break
	elif k % 2 == 0 and l[n - 1] == l[0]:
		for j in range(n - 1, -1, -1):
			if l[j] == l[0]:
				print(j + 1)
				break
	elif k % 2 == 0 and l[n - 1] != l[0]:
		for j in range(n - 1, -1, -1):
			if l[j] == l[0]:
				print(j + 1)
				break


t = int(input())
c = ''
while t > 0:
	flag = 0
	count = 0
	(n, k) = map(int, input().split())
	s = input()
	c = s[0]
	for x in s:
		j = x
		if j != c:
			c = j
			flag = 1
			count += 1
	if flag == 0:
		print('-1')
	elif count < k:
		print('-1')
	elif k % 2 == 0:
		for i in range(n - 1, 0, -1):
			if s[0] == s[i]:
				print(i + 1)
				break
	else:
		for i in range(n - 1, 0, -1):
			if s[0] != s[i]:
				print(i + 1)
				break
	t -= 1


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	s = stdin.readline()
	li = [s[0]]
	(r, key) = (k, n + 1)
	c = 0
	for i in range(1, n):
		if r == 1:
			key = i - 1
			break
		if li[-1] != s[i]:
			li.append(s[i])
			r -= 1
			key = c
		c += 1
	ind = []
	for i in range(key + 1, n):
		if li[-1] != s[i]:
			ind.append(i)
			r -= 1
	if r > 0:
		print(-1)
	else:
		print(ind[-1] + 1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, list(input())))
	prev = arr[0]
	jumps = 0
	f = -1
	for i in range(n):
		if arr[i] == (not prev):
			jumps += 1
			prev = arr[i]
		if jumps == k:
			f = i
			break
	else:
		print(-1)
	if f != -1:
		for i in range(n - 1, -1, -1):
			if arr[i] == arr[f]:
				print(i + 1)
				break


for q in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	flag = int(s[0])
	ans = -1
	temp = 0
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			temp += 1
	if not temp >= k:
		print(-1)
		continue
	for i in range(n - 1, -1, -1):
		if k % 2 == 0:
			if s[0] == s[i]:
				ans = i + 1
				break
		elif s[0] != s[i]:
			ans = i + 1
			break
	print(ans)


T = int(input())
while T > 0:
	(n, k) = map(int, input().split())
	arr = input()
	count = 0
	(last_zero, last_one) = (-1, -1)
	for i in range(n):
		if i > 0 and arr[i] != arr[i - 1]:
			count += 1
		if arr[i] == '0':
			last_zero = i
		else:
			last_one = i
	if count >= k:
		if k % 2 == 0:
			if arr[0] == '0':
				print(last_zero + 1)
			else:
				print(last_one + 1)
		elif arr[0] == '0':
			print(last_one + 1)
		else:
			print(last_zero + 1)
	else:
		print(-1)
	T -= 1


import collections
import sys

def scan():
	return list(map(int, sys.stdin.readline().strip().split()))

def solution():
	for _ in range(int(input())):
		(n, k) = scan()
		s = input()
		s = [int(i) for i in s]
		c = 0
		for i in range(1, n):
			if s[i] != s[i - 1]:
				c += 1
		if c >= k:
			for i in range(n - 1, -1, -1):
				if k % 2 == 1 and s[i] != s[0]:
					print(i + 1)
					break
				elif k % 2 == 0 and s[i] == s[0]:
					print(i + 1)
					break
		else:
			print(-1)
solution()


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	s = input()
	count = 0
	start = s[0]
	for j in range(1, N):
		if s[j] != start:
			count += 1
			if start == '0':
				start = '1'
			else:
				start = '0'
	if count >= K:
		if K % 2 == 0:
			if s[0] == '0':
				end = '0'
			else:
				end = '1'
		elif s[0] == '0':
			end = '1'
		else:
			end = '0'
		for j in range(N - 1, 0, -1):
			if s[j] == end:
				print(j + 1)
				break
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	jump = prev = 0
	for i in range(1, n):
		if s[i] != s[prev]:
			jump += 1
		prev = i
	if jump < k:
		print(-1)
	else:
		for i in range(n - 1, -1, -1):
			if k % 2 == 0 and s[i] == s[0]:
				print(i + 1)
				break
			elif k % 2 != 0 and s[i] != s[0]:
				print(i + 1)
				break


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	num = input()
	jumps = 0
	flag = num[0]
	for i in num:
		if flag != i:
			flag = i
			jumps += 1
	if jumps < k:
		print('-1')
	else:
		ans = 0
		if num[0] == '1':
			if k % 2 == 0:
				for j in range(len(num) - 1, 0, -1):
					if num[j] == '1':
						ans = j + 1
						break
			else:
				for j in range(len(num) - 1, 0, -1):
					if num[j] == '0':
						ans = j + 1
						break
		elif k % 2 == 0:
			for j in range(len(num) - 1, 0, -1):
				if num[j] == '0':
					ans = j + 1
					break
		else:
			for j in range(len(num) - 1, 0, -1):
				if num[j] == '1':
					ans = j + 1
					break
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count = len([i for i in range(1, n) if s[i] != s[i - 1]])
	if count < k:
		print(-1)
		continue
	for i in reversed(range(n)):
		if k % 2 and s[i] != s[0] or (not k % 2 and s[i] == s[0]):
			print(i + 1)
			break


try:
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		arr = input()
		c = 0
		for i in range(1, n):
			if arr[i] != arr[i - 1]:
				c += 1
		if c >= k:
			for i in range(n - 1, 0, -1):
				if k % 2 != 0 and arr[i] != arr[0]:
					print(i + 1)
					break
				elif k % 2 == 0 and arr[i] == arr[0]:
					print(i + 1)
					break
		else:
			print('-1')
except Exception as e:
	pass


t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	string = str(input())
	possible = 0
	for i in range(1, n):
		if string[i] != string[i - 1]:
			possible += 1
	if k > possible:
		print(-1)
	else:
		for i in range(n - 1, -1, -1):
			if k % 2 & (string[i] != string[0]):
				print(i + 1)
				break
			elif (k % 2 == 0) & (string[i] == string[0]):
				print(i + 1)
				break


def game(s, k):
	l = []
	li = 0
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			li += 1
			l.append(i)
	if li >= k:
		for i in range(len(s) - 1, -1, -1):
			if k % 2 == 0:
				if s[i] == s[0]:
					return i + 1
			elif s[i] != s[0]:
				return i + 1
	else:
		return -1
for i in range(int(input())):
	(N, k) = input().split(' ')
	s = input()
	print(game(s, int(k)))


T = int(input())
while T > 0:
	(N, K) = list(map(int, input().split()))
	str = input()
	ch = 0
	if int(K) > int(N):
		print(-1)
	for i in range(1, int(N)):
		if str[i] != str[i - 1]:
			ch = ch + 1
	if int(K) > int(ch):
		print(-1)
	elif ch % 2 == 0 and K % 2 == 0 or (ch % 2 != 0 and int(K) % 2 != 0):
		print(N)
	else:
		j = N - 2
		while j > 0:
			if str[j] == str[N - 1]:
				j = j - 1
			else:
				print(j + 1)
				break
	T = T - 1


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	(li, l) = ([], 0)
	p = s[0]
	for i in range(1, n):
		if s[i - 1] != s[i]:
			li.append(i)
			l += 1
	if l >= k:
		if s[0] == s[-1]:
			if k % 2:
				print(li[-1])
			else:
				print(n)
		elif k % 2:
			print(n)
		else:
			print(li[-1])
	else:
		print(-1)


t = int(input())

def check(s):
	count = 0
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			count += 1
	return count
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	str = input()
	count = check(str)
	if count < k:
		print(-1)
	elif str[0] == '1':
		if k % 2 == 0:
			print(str.rindex('1') + 1)
		else:
			print(str.rindex('0') + 1)
	elif k % 2 == 0:
		print(str.rindex('0') + 1)
	else:
		print(str.rindex('1') + 1)


def check(n, k, arr):
	sharma = ''
	s = '2'
	for i in arr:
		if i != s:
			sharma += i
			s = i
	if len(sharma) - 1 < k:
		return -1
	if sharma[0] == '1':
		if k % 2 == 0:
			val = '1'
		else:
			val = '0'
	elif k % 2 == 0:
		val = '0'
	else:
		val = '1'
	index = 0
	for i in range(n):
		if arr[i] == val:
			index = i
	index += 1
	return index
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = input()
	print(check(n, k, arr))


for i in range(int(input())):
	(N, K) = map(int, input().split())
	s = input()
	count = 0
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			count += 1
	if count >= K:
		for i in range(len(s) - 1, -1, -1):
			if K % 2 == 0 and s[i] == s[0]:
				print(i + 1)
				break
			elif K % 2 != 0 and s[i] != s[0]:
				print(i + 1)
				break
	else:
		print('-1')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	c = 0
	an = -1
	h = '0'
	for i in range(1, n):
		if a[i - 1] != a[i] and c < k:
			c += 1
			an = i + 1
			h = a[i]
		if c == k and a[i] == h:
			an = i + 1
	if c == k:
		print(an)
	else:
		print('-1')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	count = 0
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			count += 1
	if count < k:
		print(-1)
	elif k % 2 == 0:
		i = n - 1
		while a[0] != a[i]:
			i -= 1
		print(i + 1)
	else:
		i = n - 1
		while a[0] == a[i]:
			i -= 1
		print(i + 1)


for _ in range(int(input())):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	s = input()
	cn = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			cn += 1
	if cn >= k:
		for i in range(n - 1, -1, -1):
			if k % 2 == 0 and s[i] == s[0]:
				print(i + 1)
				break
			elif k % 2 != 0 and s[i] != s[0]:
				print(i + 1)
				break
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	if len(set(s)) == 1:
		print(-1)
		continue
	curr_z = -1
	curr_o = -1
	if s[0] == '0':
		nexti = 0
	else:
		nexti = 1
	count = -1
	for i in range(n):
		if s[i] == '0' and nexti == 0:
			if count < k:
				curr_z = i
				count += 1
				nexti = 1
		elif s[i] == '0' and nexti == 1:
			curr_z = i
		elif s[i] == '1' and nexti == 1:
			if count < k:
				curr_o = i
				count += 1
				nexti = 0
		elif s[i] == '1' and nexti == 0:
			curr_o = i
	if count < k:
		ans = -1
	elif count == k:
		if nexti == 1:
			ans = curr_z + 1
		else:
			ans = curr_o + 1
	print(ans)


for u in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	p = s[0]
	for i in range(1, n):
		if s[i] != p:
			c += 1
			p = s[i]
	if c < k:
		print(-1)
		continue
	if s[0] == '0':
		if k % 2 == 0:
			for i in range(n - 1, -1, -1):
				if s[i] == '0':
					print(i + 1)
					break
		else:
			for i in range(n - 1, -1, -1):
				if s[i] == '1':
					print(i + 1)
					break
	elif k % 2 == 0:
		for i in range(n - 1, -1, -1):
			if s[i] == '1':
				print(i + 1)
				break
	else:
		for i in range(n - 1, -1, -1):
			if s[i] == '0':
				print(i + 1)
				break


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s1 = s[::-1]
	c = 0
	for i in range(1, n):
		if s[i - 1] != s[i]:
			c += 1
	if c < k:
		print('-1')
	elif s[0] == '1':
		if k % 2 == 0:
			print(n - s1.index('1'))
		else:
			print(n - s1.index('0'))
	elif k % 2 == 0:
		print(n - s1.index('0'))
	else:
		print(n - s1.index('1'))


def zebra(arr, N, K):
	a = 0
	for i in range(N - 1):
		if arr[i] != arr[i + 1]:
			a += 1
	if a < K:
		print(-1)
		return
	i = N - 1
	while i >= 0:
		if K % 2 == 0:
			if arr[0] == arr[i]:
				print(i + 1)
				return
		elif arr[0] != arr[i]:
			print(i + 1)
			return
		i -= 1
T = int(input())
p1 = 0
for i in range(T * 2):
	if p1 == 0:
		(N, K) = input().strip().split()
		N = int(N)
		K = int(K)
		p1 += 1
	else:
		p1 -= 1
		str = input()
		str = [int(i) for i in str]
		zebra(str, N, K)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	curr = s[0]
	for i in s[1:]:
		if i != curr:
			curr = i
			count += 1
	if k > count:
		print(-1)
	else:
		if k % 2 == 0:
			target = s[0]
		else:
			target = str(1 - int(s[0]))
		for i in range(1, n):
			if s[-i] == target:
				print(n - i + 1)
				break


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	crossing = 0
	lzero = 0
	lone = 0
	for i in range(N):
		if i != N - 1 and S[i] != S[i + 1]:
			crossing += 1
		if S[i] == '0':
			lzero = i
		else:
			lone = i
	if crossing < K:
		print(-1)
	else:
		print(lone + 1 if int(S[0]) + K & 1 else lzero + 1)


t = int(input())
for i in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	s = input()
	count = 0
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			count += 1
	if count >= k:
		if k % 2 == 0:
			for j in range(len(s) - 1, 0, -1):
				if s[j] == s[0]:
					print(j + 1)
					break
		else:
			for j in range(len(s) - 1, 0, -1):
				if s[j] != s[0]:
					print(j + 1)
					break
	else:
		print('-1')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	if a.count('0') == 0 or a.count('1') == 0:
		print(-1)
	else:
		s = 0
		s += a.count('10')
		s += a.count('01')
		if k > s:
			print(-1)
		elif a[0] == '1':
			if k % 2 == 0:
				print(a.rfind('1') + 1)
			else:
				print(a.rfind('0') + 1)
		elif k % 2 == 0:
			print(a.rfind('0') + 1)
		else:
			print(a.rfind('1') + 1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	last = s[0]
	for i in range(1, n):
		if s[i] != last:
			count += 1
			last = s[i]
			farthest = i
	if count < k:
		print(-1)
	else:
		for j in range(n - 1, -1, -1):
			if k % 2 == 0:
				if s[j] == s[0]:
					print(j + 1)
					break
			elif s[j] != s[0]:
				print(j + 1)
				break


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	c = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			c += 1
	if c >= k:
		s1 = s[::-1]
		for i in range(n - 1, 0, -1):
			if k % 2 != 0 and s[i] != s[0]:
				print(i + 1)
				break
			elif k % 2 == 0 and s[i] == s[0]:
				print(i + 1)
				break
	else:
		print(-1)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			count += 1
	if count >= k:
		Find = s[0]
		if k % 2 != 0:
			if Find == '0':
				Find = '1'
			else:
				Find = '0'
		for i in range(n - 1, -1, -1):
			if s[i] == Find:
				print(i + 1)
				break
	else:
		print(-1)
	t -= 1


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	n = input()
	count = 0
	for i in range(N - 1):
		if n[i] != n[i + 1]:
			count += 1
	if count >= K:
		for i in range(N - 1, 0, -1):
			if K % 2 == 0:
				if n[i] == n[0]:
					print(i + 1)
					break
			elif n[i] != n[0]:
				print(i + 1)
				break
	else:
		print(-1)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	binary = input()
	possible_jumps = sum([binary[i - 1] != binary[i] for i in range(1, N)])
	if possible_jumps < K:
		print(-1)
	else:
		if K % 2 == 0:
			pos = binary[0]
		else:
			pos = ['1', '0'][binary[0] == '1']
		while N:
			if binary[N - 1] == pos:
				print(N)
				break
			N -= 1


import math
import bisect
import collections

def combination(n, r):
	return math.comb(n, r)

def listing():
	return list(map(int, input().split()))

def intp():
	return int(input())

def inp():
	return input()

def inpspl():
	return input().split()

def mapping():
	return map(int, input().split(' '))

def sqrt(n):
	return math.sqrt(n)

def gcd(a, b):
	return math.gcd(a, b)

def lcm(a, b):
	return a * b // gcd(a, b)

def p(s):
	print(f'{s}')

def lsetl(lst):
	return list(set(lst))

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(abs(n - r))

def frequencyofall(lst):
	return dict(collections.Counter(lst))

def ispowerof2(n):
	return n & n - 1 == 0

def ispowerof3(n):
	return math.log10(n) / math.log10(3) % 1 == 0

def dictionarysort(d):
	return collections.OrderedDict(sorted(d.items()))

def bintoint(s):
	return int(s, 2)

def solve():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input()
		if s.count('0') == n or s.count('1') == n:
			print(-1)
			continue
		fb = s[0]
		count = 0
		for i in range(1, n):
			if s[i - 1] != s[i]:
				count += 1
		if count < k:
			print(-1)
			continue
		for i in range(n - 1, -1, -1):
			if k % 2 == 0:
				if s[i] == fb:
					print(i + 1)
					break
			elif s[i] != fb:
				print(i + 1)
				break
solve()


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		la = input()
		count = 0
		for i in range(1, len(la)):
			if la[i] != la[i - 1]:
				count += 1
		if count >= k:
			if k % 2 == 0:
				for i in range(n - 1, -1, -1):
					if la[i] == la[0]:
						print(i + 1)
						break
			else:
				for i in range(n - 1, -1, -1):
					if la[i] != la[0]:
						print(i + 1)
						break
		else:
			print('-1')
except Exception:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	pval = s[0]
	nval = None
	c = 0
	for nval in s:
		if nval != pval:
			c += 1
			pval = nval
	if c >= k:
		if k % 2 == 0:
			for i in range(n - 1, -1, -1):
				if s[0] == s[i]:
					print(i + 1)
					break
		else:
			for i in range(n - 1, -1, -1):
				if s[0] != s[i]:
					print(i + 1)
					break
	else:
		print(-1)