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

Given a binary string $S$ consisting of $0's$ and $1's$, find whether there exists a rightwise  [circular rotation] of the string such that every 2 adjacent $1's$ are separated by at most $C$ $0's$.

Note: The last occurrence of $1$ in the rotated string won't have any $1$ next to it, i.e, first and the last ones in the string are not considered to be adjacent.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains of two lines of input.
First line contains two space separated integers $N, C$, length of the string and the upper limit on a number of $0's$ between $2$ adjacent $1's$.
Second line contains the binary string $S$.

------ Output: ------
For each testcase, output in a single line "YES" if there exists a rightwise circular rotation of string satisfying the criteria and "NO" if it doesn't exist.

Note: The output is case-insensitive ― each letter may be printed in upper case or lower case.

------ Constraints  ------
$1 ≤ N ≤ 5*10^{5}$
$0 ≤ C ≤ max(0, N - 2)$
Sum of $N$ over all tests is atmost $10^{6}$.

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

4 1

1100

4 0

0101

6 1

101001
----- Sample Output 1 ------ 
YES

NO

YES
----- explanation 1 ------ 
Case 1: In the original configuration maximum number of $0's$ between $2$ adjacent $1's$ is $0$, therefore it satisfies the criteria.

Case 2: The $4$ circular rotations of the string S = {"0101", "1010", "0101", "1010"}. In all the cases the maximum number of $0's$ between $2$ consecutive $1's$ is $1$ which doesn't satisfies the criteria.

Case 3: The $6$ circular rotations of the string S = {"101001", "110100", "011010", "001101", "100110", "010011"} out of which $second$, $third$ and $fourth$ strings satisfy the criteria.

Source: codechef | Difficulty: HARD
Tags: String algorithms

Data structures


Solutions:
for _ in range(int(input())):
	(l, c) = map(int, input().split(' '))
	s = input()
	mgap = 0
	curr = 0
	gaps = []
	i = 0
	while i < l:
		while i < l and s[i] == '0':
			curr += 1
			i += 1
		gaps.append(curr)
		i += 1
		curr = 0
	if s[-1] == '1':
		gaps.append(curr)
	gaps[0] += gaps[-1]
	gaps.pop()
	count = 0
	for j in gaps:
		if j > c:
			count += 1
	print('YES' if count < 2 else 'NO')


T = int(input())
for i in range(T):
	(n, c) = map(int, input().split())
	s = input()
	s1 = s.split('1')
	l1 = []
	if s.count('1') == 0 or s.count('1') == 1:
		print('YES')
	else:
		for i in s1:
			l1.append(len(i))
		if s[0] == '0' and s[-1] == '0':
			l1[0] = l1[-1] + l1[0]
			l1.pop()
		l1.sort()
		l1.pop()
		if c < max(l1):
			print('NO')
		else:
			print('YES')


for T in range(int(input())):
	(N, C) = map(int, input().split())
	A = input()
	S = A.split('1')
	a = []
	if A.count('1') == 1 or A.count('1') == 0:
		print('YES')
	else:
		for i in S:
			a.append(len(i))
		if A[0] == '0' and A[-1] == '0':
			a[0] = a[-1] + a[0]
			a.pop()
		a.sort()
		a.pop()
		if C < max(a):
			print('NO')
		else:
			print('YES')


import math
for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = list(map(str, input().strip('')))
	gaps = 0
	i = 0
	ind1 = 0
	if s[0] == '0':
		while ind1 < n and s[ind1] != '1':
			i += 1
			ind1 += 1
	j = 0
	ind2 = n - 1
	if s[n - 1] == '0':
		while ind2 >= 0 and s[ind2] != '1':
			j += 1
			ind2 -= 1
	if i + j == 2 * n:
		print('YES')
	else:
		if i + j > c:
			gaps += 1
		ind = ind1
		while ind <= ind2:
			if s[ind] == '0':
				y = 0
				while ind <= ind2 and s[ind] == '0':
					y += 1
					ind += 1
				if y > c:
					gaps += 1
			else:
				ind += 1
				y = 0
		if gaps >= 2:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = str(input())
	posArr = []
	for i in range(n):
		if s[i] == '1':
			posArr.append(i)
	cnt = 0
	for i in range(len(posArr) - 1):
		x = posArr[i + 1] - posArr[i] - 1
		if x > c:
			cnt += 1
	if posArr and n - 1 - posArr[-1] + posArr[0] > c:
		cnt += 1
	if cnt <= 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().strip().split())
	l = input()
	l1 = []
	for i in range(len(l)):
		if l[i] == '1':
			l1.append(i)
	count = 0
	for i in range(len(l1) - 1):
		if l1[i + 1] - l1[i] - 1 > c:
			count += 1
	if l1 and n - 1 - l1[-1] + l1[0] > c:
		count += 1
	if count <= 1:
		print('YES')
	else:
		print('NO')


N = int(input())
for _ in range(N):
	(n, c) = map(int, input().split())
	s = input()
	pos = [i for (i, p) in enumerate(s) if p == '1']
	if len(pos) == 0:
		print('YES')
		continue
	nd = 0
	for j in range(len(pos) - 1):
		d = pos[j + 1] - pos[j] - 1
		if d > c:
			nd += 1
	if nd == 0:
		print('YES')
	elif nd > 1:
		print('NO')
	elif n - pos[-1] + pos[0] - 1 > c:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	s = input()
	gapc = 0
	try:
		ind = s.index('1')
	except:
		print('YES')
		continue
	f = ind
	ans = 'YES'
	for i in range(ind + 1, n):
		if s[i] == '1':
			if i - f > c + 1:
				gapc += 1
				if gapc > 1:
					ans = 'NO'
					f = i
					break
			f = i
	if n - (f + 1) + ind > c and gapc >= 1:
		gapc += 1
		print('NO')
		continue
	print(ans)


import sys
inp = sys.stdin.readline()
test = int(inp.strip('\n'))
result = ''
for _ in range(test):
	inp = sys.stdin.readline()
	l = list(map(int, inp.strip('\n').split()))
	(n, c) = l
	inp = sys.stdin.readline()
	arr = inp.strip('\n')
	start = dist = count = last = 0
	first = True
	for i in range(n):
		if arr[i] == '1':
			if first:
				start = i
				first = False
				dist = 0
			if dist > c:
				count += 1
			dist = 0
		else:
			dist += 1
	if dist + start > c:
		count += 1
	if count > 1:
		sys.stdout.write('NO\n')
	else:
		sys.stdout.write('YES\n')


def greater_dist_count(s, c):
	(count, last_index) = (0, 0)
	for i in range(1, len(s)):
		if s[i] == '1':
			dist = i - last_index - 1
			if dist > c:
				count += 1
			last_index = i
	if len(s) - s.rfind('1') - 1 > c:
		count += 1
	return count
t = int(input())
while t > 0:
	t -= 1
	(n, c) = list(map(int, input().split(' ')))
	s = input()
	if s.find('1') == -1:
		print('YES')
	else:
		s = s[s.find('1'):] + s[:s.find('1')]
		if greater_dist_count(s, c) > 1:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	st = input()
	idx = []
	for i in range(n):
		if st[i] == '1':
			idx.append(i)
	cnt = 0
	in_idx = len(idx)
	for i in range(in_idx - 1):
		if idx[i + 1] - idx[i] - 1 > c:
			cnt += 1
	if cnt > 1:
		print('NO')
	elif cnt == 1 and n - 1 - idx[in_idx - 1] + idx[0] > c:
		print('NO')
	else:
		print('YES')


try:
	t = int(input())
	for _ in range(t):
		(n, c) = map(int, input().split())
		s = input()
		res = []
		count = 0
		for i in range(len(s)):
			if s[i] == '1':
				res.append(i)
		for i in range(len(res) - 1):
			if res[i + 1] - res[i] - 1 > c:
				count += 1
		if count > 1:
			print('NO')
			continue
		if count == 1 and n - 1 - res[-1] + res[0] > c:
			print('NO')
		else:
			print('YES')
except:
	pass


def prog_name():
	(n, c) = map(int, input().split())
	s = input()
	l = []
	cc = 0
	for x in range(len(s)):
		if s[x] == '1':
			l.append(x)
	for y in range(len(l) - 1):
		if l[y + 1] - l[y] - 1 > c:
			cc += 1
	if cc > 1:
		print('NO')
	elif cc == 1 and n - 1 - l[-1] + l[0] > c:
		print('NO')
	else:
		print('YES')
t = int(input())
for unique in range(t):
	prog_name()


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	s = input()
	count = 0
	i = 0
	f = 0
	arr = []
	while i < n:
		if s[i] == '1':
			arr.append(i)
		i = i + 1
	for i in range(1, len(arr)):
		if arr[i] - arr[i - 1] - 1 > c:
			count = count + 1
	if count > 1:
		print('NO')
		continue
	if count == 1 and n - 1 - arr[-1] + arr[0] > c:
		print('NO')
	else:
		print('YES')


import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import deque
for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = input()
	arr = []
	for i in range(n):
		if s[i] == '1':
			arr.append(i)
	cnt = 0
	for i in range(1, len(arr)):
		if arr[i] - arr[i - 1] - 1 > c:
			cnt += 1
	if cnt > 1:
		print('NO')
		continue
	if cnt == 1 and n - 1 - arr[-1] + arr[0] > c:
		print('NO')
	else:
		print('YES')


for tc in range(int(input())):
	ls = list(map(int, input().split()))
	n = ls[0]
	c = ls[1]
	st = input()
	arr = []
	for i in range(n):
		if st[i] == '1':
			arr.append(i)
	cnt = 0
	for i in range(1, len(arr)):
		if arr[i] - arr[i - 1] - 1 > c:
			cnt += 1
	if cnt > 1:
		print('NO')
		continue
	if cnt == 1 and n - 1 - arr[-1] + arr[0] > c:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = input()
	l = []
	for i in range(n):
		if s[i] == '1':
			l.append(i)
	count = 0
	for i in range(len(l) - 1):
		if l[i + 1] - l[i] - 1 > c:
			count += 1
	if count > 1:
		print('NO')
		continue
	elif count == 1 and n - 1 - l[-1] + l[0] > c:
		print('NO')
		continue
	print('YES')


from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
input = stdin.readline
prin = stdout.write
from random import sample
t = int(input())
from collections import Counter, deque
from math import sqrt, ceil, log2, gcd

class DisjSet:

	def __init__(self, n):
		self.rank = [1] * n
		self.parent = [i for i in range(n)]

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		xset = self.find(x)
		yset = self.find(y)
		if xset == yset:
			return
		if self.rank[xset] < self.rank[yset]:
			self.parent[xset] = yset
		elif self.rank[xset] > self.rank[yset]:
			self.parent[yset] = xset
		else:
			self.parent[yset] = xset
			self.rank[xset] = self.rank[xset] + 1

def f(arr, i, j, d, dist):
	if i == j:
		return
	nn = max(arr[i:j])
	for tl in range(i, j):
		if arr[tl] == nn:
			dist[tl] = d
			f(arr, i, tl, d + 1, dist)
			f(arr, tl + 1, j, d + 1, dist)

def ps(n):
	cp = 0
	while n % 2 == 0:
		n = n // 2
		cp += 1
	for ps in range(3, ceil(sqrt(n)) + 1, 2):
		while n % ps == 0:
			n = n // ps
			cp += 1
	if n != 1:
		return False
	return True

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def factorials(n, r):
	slr = n
	dpr = r
	qlr = 1
	qs = 1
	mod = 10 ** 9 + 7
	for ip in range(n - r + 1, n + 1):
		qlr = qlr * ip % mod
	for ij in range(1, r + 1):
		qs = qs * ij % mod
	ans = qlr * modInverse(qs) % mod
	return ans

def modInverse(b):
	qr = 10 ** 9 + 7
	return pow(b, qr - 2, qr)
tt = [xa ** 3 for xa in range(0, 10 ** 4 + 1)]
qq = set(tt)

def digits(k, rp):
	n = len(k)
	pq = k[::-1]
	jq = ''
	for ij in pq:
		if ij == '1':
			jq += '1'
		elif ij == '2':
			jq += '5'
		elif ij == '4' or ij == '7' or ij == '3' or (ij == '6') or (ij == '9'):
			jq += '-'
		elif ij == '5':
			jq += '2'
		elif ij == '8':
			jq += '8'
		elif ij == '0':
			jq += '0'
	if jq.find('-') != -1:
		return -1
	else:
		jl = int(jq)
		if jl >= rp:
			return -1
		else:
			return jq

def fr(a, b, h, m):
	kl = int(b)
	kl = (kl + 1) % m
	b = '0' * (2 - len(str(kl))) + str(kl)
	if b == '0' * 2:
		kj = (int(a) + 1) % h
		a = '0' * (2 - len(str(kj))) + str(kj)
	return [a, b]

def ilist():
	return [int(x) for x in input().strip().split()]

def outstrlist(array: list) -> str:
	array = [str(x) for x in array]
	return ' '.join(array)

def islist():
	return list(map(str, input().split().rstrip()))

def outfast(arr: list) -> str:
	ss = ''
	for ip in arr:
		ss += str(ip) + ' '
	return prin.write(ss)
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
for jj in range(t):
	(n, c) = ilist()
	kp = input()
	arr = []
	for ij in range(n):
		if kp[ij] == '1':
			arr.append(ij)
	brr = []
	ones = len(arr)
	if len(arr) == 0 or len(arr) == 1:
		print('YES')
		continue
	for i in range(ones):
		if i != ones - 1:
			brr.append(arr[i + 1] - arr[i] - 1)
		else:
			brr.append(n - 1 - arr[ones - 1] + arr[0] - 0)
	brr = sorted(brr)
	if brr[-2] > c:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, c) = [int(x) for x in input().split(' ')]
	s = input()
	if len(set(s)) == 1 and s[0] == '0':
		print('YES')
		continue
	index_of_ones = [i for i in range(n) if s[i] == '1']
	count = 0
	for i in range(len(index_of_ones) - 1):
		if index_of_ones[i + 1] - index_of_ones[i] - 1 > c:
			count += 1
	zeroes_at_end = s[index_of_ones[len(index_of_ones) - 1]:].count('0')
	zeroes_at_beg = s[:index_of_ones[0] + 1].count('0')
	if zeroes_at_beg + zeroes_at_end > c:
		count += 1
	if count <= 1:
		print('YES')
	else:
		print('NO')


def solve(c, n, bs):
	errstr = '0' * (c + 1) + '1'
	if int(bs.count(errstr)) > 2:
		print('NO')
	else:
		print('YES')
t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	bs = input()
	solve(c, n, bs * 2)


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	l = []
	s = input()
	cnt = 0
	for x in range(len(s)):
		if s[x] == '1':
			l.append(x)
	for x in range(1, len(l)):
		if l[x] - l[x - 1] - 1 > c:
			cnt += 1
	if cnt > 1:
		print('NO')
		continue
	if cnt == 1 and n - 1 - l[len(l) - 1] + l[0] > c:
		print('NO')
	else:
		print('YES')


for test in range(int(input())):
	(N, C) = map(int, input().split())
	S = input()
	lis = []
	c = 0
	lis[:] = S
	count = 0
	one = []
	l = len(lis)
	for i in range(l):
		if lis[i] == '1':
			one.append(i + 1)
	l1 = len(one)
	if l1 < 2:
		print('YES')
		continue
	for i in range(1, l1):
		if one[i] - one[i - 1] - 1 > C:
			count += 1
	if N - one[l1 - 1] + one[0] - 1 > C:
		count += 1
	if count > 1:
		print('NO')
	else:
		print('YES')


T = int(input())
for _ in range(T):
	(N, C) = map(int, input().split())
	S = input()
	pos = []
	for i in range(N):
		if S[i] != '0':
			pos.append(i)
	cnt = 0
	for i in range(len(pos) - 1):
		if pos[i + 1] - pos[i] - 1 > C:
			cnt += 1
	if len(pos) != 0 and N - pos[-1] + pos[0] - 1 > C:
		cnt += 1
	if cnt <= 1:
		print('YES')
	else:
		print('NO')


import sys

def solve():
	(n, tmp) = map(int, input().split())
	a = str(input())
	b = [0, 0]
	count = 0
	st = 0
	j = 0
	for i in range(n):
		if a[i] == '1':
			j = i + 1
			break
		else:
			st += 1
	for i in range(j, n):
		if a[i] == '0':
			count += 1
		else:
			b.append(count)
			count = 0
	b.append(count + st)
	b.sort()
	if b[len(b) - 2] <= tmp:
		print('YES')
	else:
		print('NO')

def main():
	test_case = int(input())
	for test in range(test_case):
		solve()
main()


def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
t = int(input())
while t > 0:
	(n, c) = map(int, input().split())
	s = input()
	for i in range(n):
		if s[i] == '1':
			break
	a = i
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			break
	b = i
	dd = a + (n - b - 1)
	if a == b:
		print('YES')
	else:
		k = 0
		d = 0
		for i in range(a + 1, b + 1):
			if s[i] == '0':
				d += 1
			else:
				if d > c:
					k += 1
				d = 0
		if dd > c:
			if k > 0:
				print('NO')
			else:
				print('YES')
		elif k > 1:
			print('NO')
		else:
			print('YES')
	t -= 1


for i in range(int(input())):
	(n, c) = map(int, input().split())
	l = input()
	idx = []
	d = 0
	for j in range(len(l)):
		if l[j] == '1':
			idx.append(j)
	print
	for j in range(len(idx) - 1):
		if idx[j + 1] - idx[j] - 1 > c:
			d += 1
	if idx and n - idx[-1] - 1 + idx[0] > c:
		d += 1
	if d > 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = input()
	arr = []
	for i in range(n):
		if s[i] == '1':
			arr.append(i)
	cnt = 0
	for i in range(1, len(arr)):
		if arr[i] - arr[i - 1] - 1 > c:
			cnt += 1
	if cnt > 1:
		print('NO')
		continue
	if cnt == 1 and n - 1 - arr[-1] + arr[0] > c:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	stack = []
	(n, c) = map(int, input().split())
	l = input().strip()
	co = 0
	stack = []
	for i in range(n):
		if l[i] == '1':
			stack.append(i)
	for i in range(len(stack) - 1):
		if stack[i + 1] - stack[i] - 1 > c:
			co += 1
	if stack and n - stack[-1] - 1 + stack[0] > c:
		co += 1
	if co <= 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = list(input())
	s = list(map(int, s))
	one_index = []
	if n == 1 and c == 0:
		print('YES')
	elif n == 1 and c > 0:
		print('NO')
	elif n > 1:
		for i in range(len(s)):
			if s[i] == 1:
				one_index.append(i)
		temp = []
		if len(one_index) >= 2:
			for i in range(1, len(one_index)):
				temp.append(one_index[i] - one_index[i - 1] - 1)
			temp.append(n - 1 - one_index[-1] + one_index[0])
		else:
			print('YES')
			continue
		ans = 0
		for i in temp:
			if i > c:
				ans += 1
		print('NO') if ans > 1 else print('YES')


t = int(input())
for i in range(t):
	(n, c) = map(int, input().split())
	s = input()
	s += s
	n = 2 * n
	count = 0
	ans = 0
	for j in range(n):
		if s[j] == '1':
			if count > c:
				ans += 1
			count = 0
		else:
			count += 1
	if ans > 2:
		print('NO')
	else:
		print('YES')


def valid_string():
	T = int(input())
	for _ in range(0, T):
		(N, C) = input().split()
		C = int(C)
		N = int(N)
		S = input()
		pos = [i for (i, d) in enumerate(S) if d == '1']
		ct = 0
		for (i, value) in enumerate(pos[0:-1]):
			if pos[i + 1] - pos[i] - 1 > C:
				ct += 1
		if len(pos) > 0 and N - pos[-1] - 1 + pos[0] > C:
			ct += 1
		if ct > 1:
			print('NO')
		else:
			print('YES')
valid_string()


t = int(input())
while t > 0:
	(n, c) = [int(x) for x in input().split()]
	s = input()
	index = s.find('1')
	s = s[index + 1:] + s[:index + 1]
	(count, prob) = (0, 0)
	for i in s:
		if i == '1':
			if count > c:
				prob += 1
			count = 0
		else:
			count += 1
	if prob > 1:
		print('NO')
	else:
		print('YES')
	t -= 1


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	s = input()
	count = 0
	dummy = s[:]
	dummy = dummy.strip('0')
	if n - len(dummy) > c:
		count += 1
	start = 0
	for i in range(1, len(dummy)):
		if dummy[i] == '1':
			if i - start - 1 > c:
				count += 1
			start = i
	if count > 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	flag = 0
	index = -1
	for i in range(n):
		if s[i] == '1':
			if index == -1:
				index = i
			else:
				if i - index - 1 > k:
					flag += 1
				index = i
	if flag > 1:
		print('NO')
	elif flag == 0:
		print('YES')
	else:
		e = 0
		i = n - 1
		while i >= 0 and s[i] == '0':
			i -= 1
			e += 1
		i = 0
		while i < n and s[i] == '0':
			i += 1
			e += 1
		if e <= k:
			print('YES')
		else:
			print('NO')


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	s = input()
	l = []
	c = 0
	f = 0
	st = 0
	lt = 0
	for i in s:
		if i == '1':
			if f:
				l.append(c)
				c = 0
			else:
				f = 1
				st = c
				c = 0
		else:
			c += 1
	lt = c
	if st and lt:
		l.append(st + lt)
	else:
		l.append(max(st, lt))
	cc = 0
	for i in l:
		if i > m:
			cc += 1
	if cc > 1:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	(n, c1) = list(map(int, input().split()))
	s = input()
	c = 0
	i = 0
	a = []
	while i < n:
		if s[i] == '0':
			c += 1
		else:
			if c != 0:
				a.append(c)
			c = 0
		i += 1
	if c != 0:
		a.append(c)
	if s[0] == '0':
		if s[len(s) - 1] == '0':
			a[0] += a[len(a) - 1]
			a = a[0:len(a) - 1]
	if len(a) == 0:
		print('YES')
	else:
		count = 0
		for i in range(len(a)):
			if a[i] > c1:
				count += 1
		if count <= 1:
			print('YES')
		else:
			print('NO')


T = int(input())
for i in range(T):
	Arr = list(map(int, input().split()))
	N = Arr[0]
	C = Arr[1]
	cnt1 = 0
	cnt2 = 0
	cnt3 = 0
	flag = 0
	A = list(input())
	for j in range(N):
		if A[j] == '1':
			if cnt1 > C:
				cnt2 += 1
			cnt1 = 0
			flag = 1
		elif A[j] == '0' and flag == 1:
			cnt1 += 1
	for j in range(N):
		if A[j] == '1':
			break
		elif A[j] == '0':
			cnt3 += 1
	for j in range(N - 1, -1, -1):
		if A[j] == '1':
			break
		elif A[j] == '0':
			cnt3 += 1
	if cnt3 > C:
		cnt2 += 1
	if cnt2 > 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	(n, c) = map(int, input().split())
	s = input()
	l = []
	for j in range(n):
		if s[j] == '1':
			l.append(j)
	m = len(l)
	if m == 0:
		print('YES')
		continue
	ans = 0
	for j in range(m - 1):
		if l[j + 1] - l[j] - 1 > c:
			ans += 1
		if ans > 1:
			break
	if n - l[m - 1] + l[0] - 1 > c:
		ans += 1
	if ans > 1:
		print('NO')
	else:
		print('YES')


t = int(input())
while t > 0:
	t -= 1
	(n, c) = map(int, input().split())
	s = str(input())
	li = []
	cnt = 0
	for i in range(0, len(s)):
		if s[i] == '1':
			li.append(i)
	for i in range(1, len(li)):
		if li[i] - li[i - 1] - 1 > c:
			cnt += 1
	if len(li) != 0 and n - li[len(li) - 1] + li[0] - 1 > c:
		cnt += 1
	if cnt <= 1:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	s = str(input())
	pos1 = []
	for j in range(a):
		if s[j] == '1':
			pos1.append(j)
	sets = 0
	for j in range(1, len(pos1)):
		if pos1[j] - pos1[j - 1] - 1 > b:
			sets += 1
	if sets > 1:
		print('NO')
	elif sets == 1 and a - pos1[-1] - 1 + pos1[0] > b:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = input().strip()
	p = [0 for i in range(n)]
	cc = 0
	k = 1
	d = {}
	for i in range(n):
		if s[i] == '0':
			cc += 1
		else:
			d[k] = cc
			k += 1
			cc = 0
	k = len(d)
	if k == 1 or k == 0:
		print('YES')
		continue
	f = 0
	for i in range(2, k):
		if d[i] > c:
			f += 1
	if f > 1:
		print('NO')
		continue
	elif f == 1 and d[k] > c:
		print('NO')
		continue
	i = n - 1
	g = 0
	while i >= 0 and s[i] != '1':
		i -= 1
		g += 1
	if f == 1 and g + d[1] > c:
		print('NO')
	elif d[k] > c and d[1] + g > c:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = input()
	one_index = []
	for i in range(len(s)):
		if s[i] == '1':
			one_index.append(i)
	res = []
	for i in range(len(one_index) - 1):
		res.append(abs(one_index[i] - one_index[i + 1]) - 1)
	zc = 0
	for i in range(len(s)):
		if s[i] == '1':
			break
		zc += 1
	for j in range(len(s) - 1, -1, -1):
		if s[j] == '1':
			break
		zc += 1
	res.append(zc)
	count = 0
	for i in res:
		if i > c:
			count += 1
	if count <= 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	(n, c) = map(int, input().split())
	s = input()
	i = []
	ans = 0
	for j in range(0, n):
		if s[j] == '1':
			i.append(j)
	for k in range(0, len(i) - 1):
		if i[k + 1] - i[k] - 1 > c:
			ans = ans + 1
	if len(i) != 0 and n - 1 - i[-1] + i[0] > c:
		ans = ans + 1
	if ans <= 1:
		print('YES')
	else:
		print('NO')
	t = t - 1


def solve(n, c, s):
	diff = []
	for i in range(n):
		if s[i] == '1':
			diff.append(i + 1)
	cnt = 0
	for i in range(len(diff) - 1):
		if diff[i + 1] - diff[i] - 1 > c:
			cnt += 1
	if len(diff) != 0 and n - diff[-1] - 1 + diff[0] > c:
		cnt += 1
	if cnt <= 1:
		return 'YES'
	return 'NO'
for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = input()
	print(solve(n, c, s))


t = int(input())
while t:
	(n, c) = map(int, input().split())
	b = input()
	ind = 0
	l = []
	for i in b:
		if i == '1':
			l.append(ind)
		ind += 1
	l2 = []
	x = 0
	if l == []:
		pass
	else:
		for i in range(len(l) - 1):
			l2.append(l[x + 1] - l[x] - 1)
			x += 1
		l2.append(n - (l[-1] - l[0] + 1))
	say = 0
	for i in l2:
		if i > c:
			say += 1
	if say > 1:
		print('NO')
	else:
		print('YES')
	t -= 1


from sys import stdin
input = stdin.readline
it = lambda : int(input())
mp = lambda : map(int, input().split())
for _ in range(it()):
	(a, b) = mp()
	k = input().strip()
	from itertools import groupby
	l = k.strip('0')
	tot = 0
	if len(k) - len(l) > b:
		tot += 1
	rem = list(l)
	cnt = 0
	while rem:
		cur = rem.pop()
		if cur == '0':
			cnt += 1
		else:
			if cnt > b:
				tot += 1
			cnt = 0
		if tot > 1:
			break
	if tot <= 1:
		print('YES')
	else:
		print('NO')


def string(c, s):
	pos1 = []
	for i in range(len(s)):
		if s[i] == '1':
			pos1.append(i)
	cnt = 0
	for i in range(len(pos1) - 1):
		if pos1[i + 1] - pos1[i] - 1 > c:
			cnt += 1
	if cnt > 1:
		print('NO')
	elif cnt == 1 and pos1[0] + len(s) - 1 - pos1[-1] > c:
		print('NO')
	else:
		print('YES')
t = int(input())
while t:
	(n, c) = map(int, input().split())
	s = input()
	string(c, s)
	t -= 1


def work():
	(d, c) = map(int, input().split())
	a = list(map(int, list(input())))
	xx = check(a, c)
	if xx > 1:
		print('NO')
	else:
		print('YES')

def check(a, c):
	i = 0
	while i < len(a):
		if a[i] == 1:
			break
		i += 1
	s = i
	t = 0
	ocu = 0
	while i < len(a):
		if a[i] == 1:
			if t > c:
				ocu += 1
			t = 0
		else:
			t += 1
		i += 1
	if s + t > c:
		ocu += 1
	return ocu
t = int(input())
while t > 0:
	t -= 1
	work()


def main1():
	output = ''
	t = int(input())
	for i in range(t):
		(n, c) = tuple(map(int, input().split()))
		assert 1 <= n <= 500000 and 0 <= c <= max(0, n - 2)
		string = input()
		start = 0
		offset = 1
		number_of_zero = 0
		for _ in range(2 * n):
			if start >= n:
				break
			if string[start] == '1':
				if string[(start + offset) % n] == '1':
					if number_of_zero > c:
						start = start + offset
						offset = 0
					number_of_zero = 0
				else:
					number_of_zero += 1
				offset += 1
				if offset == n:
					break
			else:
				start += 1
		output += '{}\n'.format('YES' if offset == n else 'NO')
	print(output)

def main():
	output = ''
	t = int(input())
	Sum = 0
	for i in range(t):
		(n, c) = tuple(map(int, input().split()))
		assert 1 <= n <= 500000 and 0 <= c <= max(0, n - 2)
		Sum += n
		assert Sum <= 1000000
		string = input()
		count = 0
		start = 0
		for _ in range(n):
			if string[start] != '1':
				start += 1
			else:
				break
		buffer = 0
		for j in range(1, n):
			if count == 2:
				break
			if string[(j + start) % n] == '1':
				count += buffer > c
				buffer = 0
			else:
				buffer += 1
		count += buffer > c
		output += '{}\n'.format('YES' if count < 2 else 'NO')
	print(output)
main()


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	binary = input()
	lst = []
	count = 0
	for i in range(len(binary)):
		if binary[i] == '1':
			lst.append(i)
	for i in range(len(lst) - 1):
		if lst[i + 1] - lst[i] - 1 > c:
			count += 1
	if lst and n - lst[-1] - 1 + lst[0] > c:
		count += 1
	if count <= 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	s = list(input())
	ones = [i + 1 for i in range(n) if s[i] == '1']
	l = len(ones)
	if l < 2:
		print('YES')
	else:
		c = 0
		for j in range(1, l):
			if ones[j] - ones[j - 1] - 1 > k:
				c += 1
		if n - ones[l - 1] + ones[0] - 1 > k:
			c += 1
		if c > 1:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = input()
	ans = []
	for i in range(len(s)):
		if s[i] == '1':
			ans += [i]
	if len(ans) > 1:
		l = len(s) - 1 - ans[-1] + ans[0]
		ans.append(ans[-1] + l + 1)
		cnt = 0
		for i in range(1, len(ans)):
			if ans[i] - ans[i - 1] - 1 > c:
				cnt += 1
		if cnt < 2:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def prime(n):
	arr = [True] * (n + 1)
	arr[0] = False
	arr[1] = False
	for i in range(n + 1):
		if arr[i]:
			for j in range(i * i, n + 1, i):
				arr[j] = False
	return arr[n]
for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = input()
	ans = []
	for i in range(len(s)):
		if s[i] == '1':
			ans += [i]
	if len(ans) > 1:
		l = len(s) - 1 - ans[-1] + ans[0]
		ans.append(ans[-1] + l + 1)
		cnt = 0
		for i in range(1, len(ans)):
			if ans[i] - ans[i - 1] - 1 > c:
				cnt += 1
		if cnt < 2:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input()))
	diff = []
	start = True
	end = -1
	first = 0
	for i in range(n):
		if s[i] == 1:
			if start:
				first = i
				end = 0
				start = False
			else:
				diff.append(end)
				end = 0
		else:
			end += 1
	diff.append(first + end)
	ans = 0
	for i in diff:
		if i > k:
			ans += 1
	if ans <= 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, c) = list(map(int, input().split()))
	a = list(input())
	b = []
	for i in range(n):
		if a[i] == '1':
			b.append(i)
	x = 0
	for i in range(len(b) - 1):
		if b[i + 1] - b[i] - 1 > c:
			x += 1
	if x > 1:
		print('NO')
	elif x == 1 and b[0] + n - 1 - b[-1] > c:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	string = input()
	starting_zero = 0
	zero = 0
	check = 0
	for a in range(n):
		if string[a] == '1':
			starting_zero = a
			break
	for a in range(starting_zero, n):
		if string[a] == '1':
			if zero > c:
				check += 1
			zero = 0
		else:
			zero += 1
		if check > 1:
			break
	if starting_zero + zero > c:
		check += 1
	if check > 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for k in range(t):
	(n, c) = input().split(' ')
	n = int(n)
	c = int(c)
	s = input()
	left_end = 0
	right_end = 0
	i = 0
	if s[i] == '0':
		while i < len(s) and s[i] == '0':
			i += 1
			left_end += 1
	i = len(s) - 1
	if s[i] == '0':
		while i > 0 and s[i] == '0':
			i -= 1
			right_end += 1
	i = 0
	while i < len(s) and s[i] != '1':
		i += 1
	i += 1
	count = 0
	violations = 0
	while i < len(s):
		while i < len(s) and s[i] == '0':
			i += 1
			count += 1
		if i < len(s) and count > c:
			violations += 1
		count = 0
		while i < len(s) and s[i] == '1':
			i += 1
	if left_end + right_end > c:
		violations += 1
	if violations > 1:
		print('NO')
	else:
		print('YES')


st = int(input())
arr = []
strarr = []
for i in range(0, st):
	l = list(map(int, input().split(' ')[:2]))
	arr.append(l)
	str1 = input()
	strarr.append(str1[:l[0]])

def printAns(arr, strarr):
	for i in range(0, len(arr)):
		nc = arr[i]
		first1 = False
		string1 = strarr[i]
		countarr = []
		for lp2 in range(0, len(string1)):
			if string1[lp2] == '1' and (not first1):
				first1 = True
				count = 0
			elif string1[lp2] == '0' and first1:
				count += 1
			elif string1[lp2] == '1' and first1:
				countarr.append(count)
				count = 0
		key = 0
		count2 = 0
		key2 = len(string1) - 1
		while string1[key] != '1' and key < len(string1) - 1:
			count2 += 1
			key += 1
		while string1[key2] != '1' and key2 >= 0:
			count2 += 1
			key2 -= 1
		countarr.append(count2)
		if len(countarr) > 1:
			max1 = countarr[0]
			maxind = 0
			for i in range(0, len(countarr)):
				if max1 < countarr[i]:
					max1 = countarr[i]
					maxind = i
			(countarr[0], countarr[maxind]) = (countarr[maxind], countarr[0])
			max2 = countarr[1]
			for i in range(1, len(countarr)):
				if max2 < countarr[i]:
					max2 = countarr[i]
			if max2 > nc[1]:
				print('NO')
			else:
				print('YES')
		else:
			print('YES')
printAns(arr, strarr)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = input()
	flag = 0
	for i in s:
		if i == '1':
			flag = 1
			break
	if flag == 0:
		print('YES')
		continue
	a = [len(i) for i in s.split('1')]
	qu = wu = 0
	for i in range(n):
		if s[i] == '1':
			break
		qu += 1
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			break
		wu += 1
	x = qu + wu
	if wu != 0 and len(a) > 0:
		del a[-1]
	if qu != 0 and len(a) > 0:
		del a[0]
	if len(a) == 0:
		print('YES')
		continue
	if max(a) <= c:
		print('YES')
		continue
	if x > c:
		print('NO')
		continue
	a.sort()
	del a[-1]
	if len(a) > 0 and a[-1] > c:
		print('NO')
		continue
	print('YES')


def cal_violations():
	z = S.split('1')
	if len(z) > 2:
		a = z.pop(0)
		b = z.pop(-1)
		nz = [1 for f in z if len(f) > C]
		return (sum(nz), len(a), len(b))
	else:
		return (0, 0, 0)
for _ in range(int(input())):
	(N, C) = list(map(int, input().split()))
	S = input()
	(violations, a, b) = cal_violations()
	if violations == 0:
		print('YES')
	elif violations > 1:
		print('NO')
	elif a + b > C:
		print('NO')
	else:
		print('YES')


for z in range(int(input())):
	(n, c) = map(int, input().split())
	s = input().strip()
	end = -1
	l = []
	for i in range(n):
		if s[i] == '1':
			if end != -1:
				l.append(i - end - 1)
			else:
				start = i
			end = i
	count = 0
	if l:
		l.append(n - end - 1 + start)
	for i in range(len(l) - 1):
		if l[i] > c:
			count += 1
			ind = i
	if count == 0 or (count == 1 and (i + 2 != len(l) or l[-1] <= c)):
		print('YES')
	else:
		print('NO')


t = int(input())
N = [0] * t
C = [0] * t
arr = [''] * t
for i in range(t):
	(N[i], C[i]) = list(map(int, input().split()))
	arr[i] = input()
for i in range(t):
	flagg = True
	count = 0
	k = 0
	while k < len(arr[i]) and arr[i][k] == '0':
		count += 1
		k += 1
	k = len(arr[i]) - 1
	while k > 0 and arr[i][k] == '0':
		count += 1
		k -= 1
	if count > C[i]:
		flag = True
	else:
		flag = False
	count = 0
	for j in arr[i].strip('0'):
		if j == '0':
			count += 1
			continue
		if count > C[i] and flag == True:
			print('NO')
			flagg = False
			break
		if count > C[i] and flag == False:
			flag = True
		count = 0
	if flagg:
		print('YES')


for t in range(int(input())):
	(n, c) = map(int, input().split())
	s = input()
	zerogroup = 0
	c0 = 0
	c1 = 0
	i = 0
	j = n - 1
	while (s[i] != '1' or s[j] != '1') and i != n - 1:
		if s[i] == '0':
			c0 += 1
			i += 1
		if s[j] == '0':
			c0 += 1
			j -= 1
	if c0 > c:
		zerogroup += 1
	for p in range(i + 1, j + 1):
		if s[p] == '1':
			if c1 > c:
				zerogroup += 1
			c1 = 0
		elif s[p] == '0':
			c1 += 1
	if zerogroup > 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	s = input()
	e = 0
	(l, m, bc, ac) = (0, 0, 0, 0)
	for i in range(len(s)):
		if s[i] == '0':
			if l != 0:
				m += 1
			else:
				ac += 1
		elif l != 0:
			if m > c:
				if bc == 1:
					e = 1
					break
				else:
					bc = 1
					m = 0
			else:
				m = 0
		else:
			l = 1
	if e == 1:
		print('NO')
	elif ac + m > c and bc == 1 and (l == 1):
		print('NO')
	else:
		print('YES')


for rk in range(int(input())):
	(n, c) = [int(i) for i in input().split()]
	s = input()
	case = True
	se = {}
	p = 1
	for i in range(n):
		if s[i] == '1':
			se[p] = i
			p += 1
	diff = []
	for i in range(1, p):
		if i == p - 1:
			sun = n - (se[i] + 1) + se[1]
			diff.append(sun)
		else:
			sun = se[i + 1] - (se[i] + 1)
			diff.append(sun)
	time = 0
	for i in diff:
		if i <= c:
			case = True
		elif i > c and time == 0:
			time += 1
		else:
			case = False
			break
	if case == True:
		print('YES')
	else:
		print('NO')


import sys
from collections import defaultdict, deque
import math
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
INF = float('inf')
MOD = 998244353
t = 1
t = int(input())
for _ in range(t):
	(n, c) = inp()
	s = input()
	aux = []
	i = 0
	while i < n:
		if s[i] == '0':
			count = 1
			while i < n - 1 and s[i] == s[i + 1]:
				count += 1
				i += 1
			aux.append(count)
		i += 1
	if s[0] == '0' and s[n - 1] == '0':
		if len(aux) >= 2:
			f = aux.pop(0)
			l = aux.pop(len(aux) - 1)
			aux.append(f + l)
	cnt = 0
	for i in range(len(aux)):
		if aux[i] > c:
			cnt += 1
	if cnt <= 1:
		print('YES')
	else:
		print('NO')