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

"All the pain in the world will not help you find something that does not exist..."

You are Dastan, the great Prince of Persia!

Under the tunnels of Alamut, you have discovered a path ― a sequence of $N$ tiles (numbered $1$ through $N$) ahead of you. You are currently on tile $1$. There is a signboard beside you, which says thus:
Stepping on tile $i$ (for each valid $i$) activates a switch described by a binary string $S_{i}$ with length $N$. When you fell through the tunnels onto tile $1$, switch $S_{1}$ got activated.
For each valid $i$, when the switch $S_{i}$ gets activated, then for each $j$ ($1 ≤ j ≤ N)$, if the $j$-th character of $S_{i}$ is '0', tile $j$ becomes unsafe to step on; otherwise (if the $j$-th character is '1'), tile $j$ becomes safe to step on.
Step on an unsafe tile and you shall testify the fate of all men ― death!
You shall find that which you seek on reaching tile $N$. This tile must also be safe when you step on it.

Being a trained warrior, you are able to make jumps with length up to $K$ tiles, in both directions. In other words, if you are currently at a tile $i$, you may jump to a tile $j$ if $j$ is a valid tile and $|i-j| ≤ K$.

You want to reach tile $N$ as quickly as possible ― you want to minimise the number of jumps you need to make. Find this minimum number of jumps.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains a single string $S_{i}$ with length $N$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum number of jumps you need to reach your target, or $-1$ if it is impossible.

------  Constraints ------
$1 ≤ T ≤ 10^{2}$
$1 ≤ K < N ≤ 10^{3}$
$S_{1}, S_{2}, \ldots, S_{N}$ contain only characters '0' and '1'
for each valid $i$, the $i$-th digit of $S_{i}$ is '1'
the sum of $N^{2}$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (50 points):
$T ≤ 10$
$N ≤ 10$

Subtask #2 (50 points): original constraints

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

5 2

11001

01010

10101

00110

10101

3 1

110

010

011
----- Sample Output 1 ------ 
4

-1
----- explanation 1 ------ 
Example case 1: The optimal sequence of jumps is $1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5$. A shorter sequence does not exist.

Example case 2: There is no sequence of jumps that would allow you to reach tile $3$.

Source: codechef | Difficulty: HARD
Tags: Data structures

Graph algorithms

Graph traversal


Solutions:
from collections import *
for t in range(int(input())):
	(n, k) = map(int, input().split())
	susjedi = defaultdict(list)
	for i in range(n):
		s = input()
		for j in range(n):
			if abs(i - j) <= k and s[j] == '1' and (i != j):
				susjedi[i].append(j)

	def bfs(x):
		udaljenost = [-1] * n
		udaljenost[x] = 0
		q = deque()
		q.append(x)
		while len(q) > 0:
			x = q.popleft()
			for y in susjedi[x]:
				if udaljenost[y] == -1:
					udaljenost[y] = udaljenost[x] + 1
					q.append(y)
		return udaljenost[n - 1]
	print(bfs(0))


from collections import deque

def shortest_path(n, k, s):
	visited = [False] * n
	q = deque()
	visited[0] = True
	q.append((0, 0))
	while len(q) > 0:
		node = q.popleft()
		if node[0] == n - 1:
			return node[1]
		for i in range(n):
			if abs(i - node[0]) <= k and (not visited[i]) and (s[node[0]][i] == '1'):
				q.append((i, node[1] + 1))
				visited[i] = True
	return -1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = [input().strip() for _ in range(n)]
	print(shortest_path(n, k, s))


from heapq import heapify, heappush, heappop
T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	graph = [[] for i in range(n + 1)]
	m = 2 * 10 ** 3
	dis = [m] * (n + 1)
	dis[1] = 0
	h = [True] * (n + 1)
	for i in range(n):
		s = input()
		for j in range(n):
			if s[j] == '1' and abs(i - j) <= k and (i != j):
				graph[i + 1].append(j + 1)
	x = 1
	p = 1
	while p <= n:
		h[x] = False
		for i in graph[x]:
			if h[i]:
				if dis[x] + 1 < dis[i]:
					dis[i] = dis[x] + 1
		mm = m
		for i in range(n):
			if h[i]:
				if dis[i] <= mm:
					mm = dis[i]
					x = i
		p += 1
	if dis[n] != m:
		print(dis[n])
	else:
		print(-1)


from collections import deque

def bfs(start, graph):
	visited = {start}
	explored = set()
	levels = {start: 0}
	queue = deque([])
	queue.append(start)
	while len(queue) > 0:
		x = queue.popleft()
		explored.add(x)
		if x not in graph:
			continue
		for i in graph[x]:
			if i not in visited:
				visited.add(i)
				queue.append(i)
				levels[i] = levels[x] + 1
	return levels
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 1:
		print(0)
		continue
	d = {}
	for i in range(1, n + 1):
		s = input()
		j = 0
		while j < n:
			x = s[j]
			if x == '1':
				r = abs(j + 1 - i)
				if r != 0 and r <= k:
					if i in d:
						a = d[i]
						a.append(j + 1)
					else:
						d[i] = [j + 1]
			j = j + 1
		if i in d:
			continue
		else:
			d[i] = []
	v = bfs(1, d)
	if n in v:
		print(v[n])
	else:
		print(-1)


from collections import deque

def bfs(n, k, S):
	vis = [False] * n
	q = deque()
	vis[0] = True
	q.append((0, 0))
	while len(q) > 0:
		node = q.popleft()
		if node[0] == n - 1:
			return node[1]
		for i in range(n):
			if abs(i - node[0]) <= k and (not vis[i]) and (S[node[0]][i] == '1'):
				q.append((i, node[1] + 1))
				vis[i] = True
	return -1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	S = [input().strip() for _ in range(n)]
	print(bfs(n, k, S))


def bfs(start, S, N, K):
	q = [start]
	distances = [0 for i in range(N)]
	visited = [False for i in range(N)]
	visited[start] = True
	while len(q) != 0:
		x = q.pop(0)
		for i in range(N):
			if S[x][i] == '1' and visited[i] == False and (abs(x - i) <= K):
				q.append(i)
				distances[i] = distances[x] + 1
				visited[i] = True
	if visited[N - 1]:
		return distances[N - 1]
	else:
		return -1
T = int(input())
ans = []
for _ in range(T):
	(N, K) = [int(i) for i in input().split()]
	S = []
	for i in range(N):
		s = input()
		S.append(s)
	ans.append(bfs(0, S, N, K))
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	graph = [[] for i in range(n)]
	for i in range(n):
		s = input()
		r1 = max(0, i - k)
		r2 = min(n - 1, i + k)
		for j in range(r1, r2 + 1):
			if j != i and s[j] == '1':
				graph[i].append(j)
	visited = set()
	curr = 0
	queue = []
	queue.append(0)
	jumps = [-1] * n
	jumps[0] = 0
	f = 0
	while queue:
		curr = queue.pop(0)
		for g in graph[curr]:
			if g not in visited:
				visited.add(g)
				queue.append(g)
				jumps[g] = jumps[curr] + 1
				if g == n - 1:
					f = 1
					break
		if f == 1:
			break
	print(jumps[-1])


for t in range(int(input())):
	(n, k) = map(int, input().split())
	from collections import defaultdict
	graph = defaultdict(set)
	for i in range(1, n + 1):
		lis = list(input())
		lis = [int(a) for a in lis]
		tovis = set()
		for (ind, num) in enumerate(lis):
			if num == 1:
				tovis.add(ind + 1)
		for j in range(1, k + 1):
			if i + j in tovis:
				graph[i].add(i + j)
			if i - j in tovis:
				graph[i].add(i - j)
	dist = defaultdict(int)
	dist[1] = 0
	from queue import Queue
	q = Queue()
	q.put(1)
	vis = set()
	while not q.empty():
		cur = q.get()
		if n in graph[cur]:
			dist[n] = dist[cur] + 1
			break
		for neigh in graph[cur]:
			if neigh not in vis:
				vis.add(neigh)
				dist[neigh] = dist[cur] + 1
				q.put(neigh)
		if q.empty():
			dist[n] = -1
	print(dist[n])


def abs(i, j):
	if i > j:
		return i - j
	else:
		return j - i

class vertex:

	def __init__(self, col, dis):
		self.color = col
		self.d = dis
test_cases = int(input())
for _ in range(test_cases):
	(n, max_jump) = map(int, input().split())
	V = []
	Adj = {}
	for i in range(n):
		V.append(vertex('white', -1))
		Adj[V[i]] = []
	for i in range(n):
		s = input()
		for j in range(i):
			if s[j] == '1' and abs(i, j) <= max_jump:
				Adj[V[i]].append(V[j])
		for j in range(i + 1, n):
			if s[j] == '1' and abs(i, j) <= max_jump:
				Adj[V[i]].append(V[j])
	source_vertex = V[0]
	source_vertex.color = 'grey'
	source_vertex.d = 0
	Q = [source_vertex]
	front = 0
	while front != len(Q):
		dequed_vertex = Q[front]
		front += 1
		for x in Adj[dequed_vertex]:
			if x.color == 'white':
				x.d = dequed_vertex.d + 1
				x.color = 'grey'
				Q.append(x)
		dequed_vertex.color = 'black'
	print(V[n - 1].d)


from collections import deque
test = int(input())
for _ in range(test):
	(n, k) = [int(i) for i in input().split()]
	s = []
	for i in range(n):
		s.append(input())
	graph = [[] for i in range(n)]
	for i in range(len(s)):
		for j in range(max(0, i - k), min(n - 1, i + k) + 1):
			if s[i][j] == '1' and j != i:
				graph[i].append(j)
	curr = 0
	dist = [-1] * n
	dist[0] = 0
	q = deque()
	q.append(0)
	temp = 0
	vis = [0] * n
	while len(q) > 0:
		curr = q.popleft()
		for i in graph[curr]:
			if vis[i] == 1:
				continue
			vis[i] = 1
			q.append(i)
			dist[i] = dist[curr] + 1
			if i == n - 1:
				temp = 1
				break
		if temp == 1:
			break
	print(dist[n - 1])


from collections import deque
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	temp = []
	graph = {}
	for i in range(n):
		graph[i] = set()
	ans = 0
	for i in range(n):
		s = input()
		if i == 0 and s[0] == '0':
			ans = -1
			break
		prev = max(0, i - k)
		forw = min(n - 1, i + k)
		for j in range(prev, forw + 1):
			if j == i:
				continue
			if s[j] == '1':
				graph[i].add(j)
	if ans == -1:
		print(ans)
		continue
	visited = set([0])
	q = deque([(0, 0)])
	flag = False
	while len(q) > 0:
		(curr, depth) = q.popleft()
		for item in graph[curr]:
			if item not in visited:
				q.append((item, depth + 1))
				visited.add(item)
		if curr == n - 1:
			flag = True
			ans = depth
			break
	if flag:
		print(ans)
	else:
		print(-1)


import queue

def minEdgeBFS(edges, v, n):
	visited = [0] * n
	distance = [-1] * n
	Q = queue.Queue()
	distance[0] = 0
	Q.put(0)
	visited[0] = True
	while not Q.empty():
		x = Q.get()
		for i in range(len(edges[x])):
			if visited[edges[x][i]]:
				continue
			distance[edges[x][i]] = distance[x] + 1
			Q.put(edges[x][i])
			visited[edges[x][i]] = 1
	return distance[v]
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = []
	for i in range(N):
		S.append(input())
	graph = [[] for i in range(N)]
	for i in range(N):
		a = S[i]
		for j in range(max(0, i - K), min(N, i + K + 1)):
			if a[j] == '1' and i != j:
				graph[i].append(j)
	p = minEdgeBFS(graph, N - 1, N)
	print(p)


def solve(occ, n, k):
	u = 0
	queue = [u]
	dist = [0] * n
	enc = [True] + [False] * (n - 1)
	while len(queue):
		u = queue.pop(0)
		for i in occ[u]:
			if enc[i] == False and abs(i - u) <= k:
				enc[i] = True
				dist[i] = dist[u] + 1
				queue.append(i)
				if i == n - 1:
					return dist[i]
	return -1
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	occ = []
	for i in range(n):
		s1 = input()
		occ.append([])
		for j in range(n):
			if int(s1[j]) == 1:
				occ[i].append(j)
	jump = solve(occ, n, k)
	print(jump)


def createList(V, s):
	for i in range(1, V + 1):
		s[i] = []

def addEdge(x, y):
	s[x].append(y)

def BFS(s, node, queue, visited, dist, pred):
	visited[node] = 1
	dist[node] = 0
	queue.append(node)
	while queue != []:
		v = queue.pop(0)
		for i in s[v]:
			if visited[i] == 0:
				visited[i] = 1
				pred[i] = v
				dist[i] = dist[pred[i]] + 1
				queue.append(i)

def SSSP(source, dest, path, pred):
	if pred[dest] == -1:
		print(-1)
		return 0
	else:
		while dest != source:
			path.append(dest)
			dest = pred[dest]
		path.append(source)
		return 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	V = n
	s = {}
	createList(V, s)
	queue = []
	visited = [0] * (V + 1)
	dist = [-1] * (V + 1)
	pred = [-1] * (V + 1)
	path = []
	for i in range(n):
		string = input()
		length = len(string)
		j = i + 1
		while abs(j - i) <= k and j < length:
			if string[j] == '1':
				addEdge(i + 1, j + 1)
			j += 1
		j = i - 1
		while abs(j - i) <= k and j >= 0:
			if string[j] == '1':
				addEdge(i + 1, j + 1)
			j -= 1
	BFS(s, 1, queue, visited, dist, pred)
	if SSSP(1, n, path, pred):
		print(len(path) - 1)


def bfs_connected_component(graph, start):
	explored = []
	queue = [start]
	levels = {}
	levels[start] = 0
	visited = [start]
	while queue:
		node = queue.pop(0)
		explored.append(node)
		neighbours = graph[node]
		for neighbour in neighbours:
			if neighbour not in visited:
				queue.append(neighbour)
				visited.append(neighbour)
				levels[neighbour] = levels[node] + 1
	return levels
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 1:
		print(0)
		continue
	d = {}
	for i in range(1, n + 1):
		s = input()
		j = 0
		while j < n:
			x = s[j]
			if x == '1':
				r = abs(j + 1 - i)
				if r != 0 and r <= k:
					if i in d:
						a = d[i]
						a.append(j + 1)
					else:
						d[i] = [j + 1]
			j = j + 1
		if i in d:
			continue
		else:
			d[i] = []
	v = bfs_connected_component(d, 1)
	if n in v:
		print(v[n])
	else:
		print(-1)


from collections import defaultdict

class graph:

	def __init__(self):
		self.graph = defaultdict(list)

	def addedge(self, u, v):
		self.graph[u].append(v)

	def bfs(self, strt):
		global moves, flag, count
		flag = 0
		l = []
		visited = [False for i in range(n)]
		queue = []
		queue.append((strt, 0))
		visited[strt] = True
		while len(queue):
			strt = queue.pop(0)
			for i in self.graph[strt[0]]:
				if visited[i] == False:
					queue.append((i, strt[1] + 1))
					l.append((i, strt[1] + 1))
					visited[i] = True
		return l
t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	adj_mat = []
	for i in range(n):
		adj_mat.append(list(input()))
	g = graph()
	for i in range(n):
		for j in range(max(i - k, 0), min(n, i + k + 1)):
			if adj_mat[i][j] == '1' and i != j and (abs(j - i) <= k):
				g.addedge(i, j)
	count = -1
	for i in g.bfs(0):
		if i[0] == n - 1:
			count = i[1]
			break
	print(count)


def sssp_bfs(graph, visited, root, dest):
	queue = [root]
	flag = True
	visited[root] = 0
	parent[root] = -1
	distance[root] = 0
	while len(queue):
		node = queue.pop(0)
		for i in graph[node]:
			if i not in visited:
				visited[i] = 0
				parent[i] = node
				distance[i] = distance[node] + 1
				queue.append(i)
				if i == dest:
					flag = False
		if not flag:
			break
	if flag:
		return -1
	else:
		return distance[dest]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	naksha = {}
	for i in range(n):
		naksha[i + 1] = []
	for i in range(n):
		path = input()
		if i - k <= 0:
			start = 0
		else:
			start = i - k
		if i + k >= n - 1:
			end = n
		else:
			end = i + k + 1
		for j in range(start, end):
			if path[j] == '1':
				naksha[i + 1].append(j + 1)
	visited = {}
	parent = {}
	distance = {}
	print(sssp_bfs(naksha, visited, 1, n))


t = int(input())

def BFS(gra, s, n):
	visited = [False for i in range(n)]
	distance = [float('inf') for i in range(n)]
	queue = [s]
	distance[s] = 0
	visited[s] = True
	while queue:
		u = queue.pop(0)
		for v in range(max(0, u - k - 1), min(n, u + k + 1)):
			if gra[u][v] and visited[v] == False:
				queue.append(v)
				distance[v] = min(distance[v], distance[u] + 1)
				visited[v] = True
	return distance[n - 1]
for _ in range(t):
	(n, k) = map(int, input().split())
	gra = [[0 for j in range(n)] for i in range(n)]
	for i in range(n):
		s = input()
		for j in range(n):
			gra[i][j] = int(s[j])
	Min = BFS(gra, 0, n)
	if Min == float('inf'):
		print(-1)
	else:
		print(Min)


from collections import defaultdict

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def shortestDist(self, s, d):
		visited = [False] * (d + 1)
		dist = [-1] * (d + 1)
		queue = []
		visited[s] = True
		queue.append(s)
		dist[s] = 0
		while queue:
			s = queue.pop(0)
			for i in self.graph[s]:
				if not visited[i]:
					queue.append(i)
					dist[i] = dist[s] + 1
					visited[i] = True
					if i == d:
						return dist[d]
		return -1
t = int(input())
while t:
	g = Graph()
	(n, k) = map(int, input().split())
	for i in range(n):
		s = input()
		for j in range(i + 1, i + k + 1):
			if j > n - 1:
				break
			if s[j] == '1':
				g.addEdge(i, j)
		for j in range(i - 1, i - k - 1, -1):
			if j < 0:
				break
			if s[j] == '1':
				g.addEdge(i, j)
	print(g.shortestDist(0, n - 1))
	t -= 1


from queue import Queue

def chef(n, k, arr):
	que = Queue()
	que.put(1)
	dp = [100000000] * (n + 1)
	vis = [0] * (n + 1)
	dp[1] = 0
	while not que.empty():
		node = que.get()
		j = node + 1
		while j <= n and j - node <= k:
			if arr[node - 1][j - 1] == '1' and dp[j] > dp[node] + 1 and (vis[j] != 1):
				dp[j] = dp[node] + 1
				que.put(j)
			j += 1
		j = node - 1
		while j > 0 and node - j <= k:
			if arr[node - 1][j - 1] == '1' and dp[j] > dp[node] + 1 and (vis[j] != 1):
				dp[j] = dp[node] + 1
				que.put(j)
			j -= 1
		vis[node] = 1
	if dp[-1] == 100000000:
		return -1
	else:
		return dp[-1]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = []
	for _ in range(n):
		arr.append(input())
	print(chef(n, k, arr))


T = int(input())
for i in range(T):
	(N, K) = map(int, input().strip().split())
	edges = []
	for i in range(N):
		A = input().strip()
		edges.append(A)
	visited = [0] * N
	Q1 = [0]
	count = -1
	while Q1 != []:
		Q2 = Q1
		Q1 = []
		count = count + 1
		if visited[N - 1] == 1:
			break
		while Q2 != []:
			cur = Q2.pop(0)
			start = max(0, cur - K)
			end = min(N - 1, cur + K)
			for j in range(start, end + 1):
				if j == cur:
					continue
				if edges[cur][j] == '1':
					if visited[j] == 0:
						Q1.append(j)
						visited[j] = 1
						if j == N - 1:
							break
	if visited[N - 1] == 1:
		print(count)
	else:
		print(-1)


from collections import deque

def constructGraph(graph, switches, k):
	for i in range(0, n):
		curr = i
		switch = switches[i]
		lower = -1
		upper = -1
		if curr - k < 0:
			lower = 0
		else:
			lower = curr - k
		if curr + k > n - 1:
			upper = n - 1
		else:
			upper = curr + k
		for j in range(lower, upper + 1):
			if switch[j] == '1':
				graph[i + 1].append(j + 1)

def valid(curr, nxt, visited, minDist, graph):
	for v in graph[curr]:
		if not visited[v - 1] and v != curr:
			nxt.append(v)
			visited[v - 1] = True
			minDist[v - 1] = minDist[curr - 1] + 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	switches = []
	for __ in range(n):
		switches.append(input())
	graph = {}
	for ii in range(n):
		graph[ii + 1] = []
	constructGraph(graph, switches, k)
	nxt = deque([1])
	minDist = [0] * n
	visited = [False] * n
	while nxt:
		curr = nxt.popleft()
		valid(curr, nxt, visited, minDist, graph)
	res = minDist[-1]
	if res == 0:
		print(-1)
	else:
		print(res)


def steps(n, k, s):
	q = []
	v = [0] * n
	d = [100000] * n
	q.append(0)
	d[0] = 0
	v[0] = 1
	dist = 0
	while len(q) != 0:
		i = q[0]
		q.pop(0)
		t = 1
		while t <= k:
			if i + t in range(0, n):
				if s[i][i + t] == '1' and v[i + t] == 0 and (d[i] + 1 < d[i + t]):
					v[i + t] = 1
					d[i + t] = d[i] + 1
					q.append(i + t)
			if i - t in range(0, n):
				if s[i][i - t] == '1' and v[i - t] == 0 and (d[i] + 1 < d[i - t]):
					v[i - t] = 1
					d[i - t] = d[i] + 1
					q.append(i - t)
			t += 1
	if d[-1] == 100000:
		return -1
	else:
		return d[-1]
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	switch = []
	for o in range(N):
		switch.append(input())
	print(steps(N, K, switch))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	lis = []
	ans = [9999999] * n
	for __ in range(n):
		lis.append(input())
	ans[0] = 0
	possible = [0]
	covered = []
	i = 0
	while len(possible) != 0:
		i = possible[0]
		del possible[0]
		if i in covered:
			continue
		covered.append(i)
		item = lis[i]
		start = max(0, i - k)
		end = min(i + k + 1, n)
		for j in range(start, end):
			if item[j] == '1' and j != i:
				h = min(ans[i] + 1, ans[j])
				ans[j] = h
				possible.append(j)
	if ans[n - 1] == 9999999:
		print(-1)
	else:
		print(ans[n - 1])


def solve(graph, src, dest, v, k):
	res = BFS(graph, src, dest, v, k)
	return res

def BFS(graph, src, dest, v, k):
	queue = []
	visited = [False] * v
	dist = [float('inf')] * v
	pred = [-1] * v
	visited[src] = True
	dist[src] = 0
	queue.append(src)
	while queue:
		u = queue.pop(0)
		for i in graph[u]:
			if visited[i] == False and abs(i - u) <= k:
				visited[i] = True
				dist[i] = dist[u] + 1
				pred[i] = u
				queue.append(i)
				if i == dest:
					return dist[i]
	return -1
for t in range(int(input())):
	(n, k) = map(int, input().split())
	graph = []
	for i in range(n):
		s = input()
		for j in range(len(s)):
			graph.append([])
			if s[j] == '1':
				graph[i].append(j)
	res = solve(graph, 0, n - 1, n, k)
	print(res)


import sys

def bfs(graph, n):
	dist = [float('inf')] * n
	visited = [False] * n
	dist[0] = 0
	q = [0]
	while q:
		u = q.pop(0)
		for i in graph[u]:
			if visited[i] == False and abs(i - u) <= k:
				visited[i] = True
				if i == u:
					continue
				dist[i] = min(dist[u] + 1, dist[i])
				q.append(i)
				if i == n - 1:
					return dist[n - 1]
	return -1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	graph = []
	for i in range(n):
		s = sys.stdin.readline()
		temp = []
		for j in range(n):
			if s[j] == '1' and j != i:
				temp.append(j)
		graph.append(temp)
	ans = bfs(graph, n)
	print(ans)


import queue
import math
import sys

def bfs(adj, s, d, dist, n):
	q = queue.Queue(maxsize=n)
	vis = [False for i in range(n)]
	vis[s] = True
	dist[s] = 0
	q.put(s)
	while not q.empty():
		u = q.get()
		for j in adj[u]:
			if vis[j] == False:
				vis[j] = True
				dist[j] = dist[u] + 1
				q.put(j)
				if j == d:
					return True
	return False
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	for i in range(n):
		s = input()
		l.append(s)
	adj = [[] for i in range(n)]
	dist = [sys.maxsize for i in range(n)]
	sptSet = [False for i in range(n)]
	for i in range(n):
		for j in range(n):
			if abs(j - i) <= k:
				if l[i][j] == '1':
					adj[i].append(j)
	if bfs(adj, 0, n - 1, dist, n):
		print(dist[n - 1])
	else:
		print(-1)


def convert(s, c, b):
	l = []
	ini = max(0, c - b - 1)
	fin = min(len(s), c + b)
	for x in range(ini, fin):
		if s[x] == '1':
			if x == c - 1:
				continue
			else:
				l.append(x + 1)
	return l

def bfs(graph, start, end):
	(visited, queue) = (set(), [start])
	dist = [0 for i in range(end + 1)]
	c = 0
	flag = 0
	dist[start] = 0
	visited.add(start)
	while queue:
		vertex = queue.pop(0)
		for i in graph[vertex]:
			if i not in visited:
				visited.add(i)
				dist[i] = dist[vertex] + 1
				queue.append(i)
				if i == end:
					return (dist[end], True)
	return (0, False)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	d = {}
	c = 1
	for x in range(a):
		s = input()
		d[c] = convert(s, c, b)
		c += 1
	(q, w) = bfs(d, 1, a)
	if w:
		print(q)
	else:
		print(-1)


from collections import defaultdict
from os import system
import sys
system('cls')

class graph:

	def __init__(self, totNode):
		self.base = defaultdict(list)
		self.nodes = totNode

	def addEdge(self, parent, child):
		self.base[parent].append(child)

	def printGraph(self):
		print(self.base)

	def bfs(self, sourse):
		dp = [sys.maxsize] * (self.nodes + 1)
		visited = [False] * (self.nodes + 1)
		queue = [sourse]
		dp[sourse] = 0
		while queue:
			dq = queue.pop(0)
			visited[dq] = True
			for i in self.base[dq]:
				if visited[i] == False:
					queue.append(i)
					dp[i] = dp[dq] + 1
					visited[i] = True
				elif dp[i] > dp[dq] + 1:
					dp[i] = dp[dq] + 1
		if dp[self.nodes] == sys.maxsize:
			return -1
		else:
			return dp[self.nodes]
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	tree = graph(N)
	for __ in range(N):
		xx = input()
		for i in range(len(xx)):
			if xx[i] == '1':
				if i != __:
					if abs(i - __) <= K:
						tree.addEdge(__ + 1, i + 1)
	print(tree.bfs(1))


import queue

def solve_under_the_tunnels(adjacency, end):
	r = bfs(adjacency, 0, end)
	(traversal, origin, ans) = (r[0], r[1], 0)
	if end not in traversal or 0 not in traversal:
		print('-1')
	elif len(traversal) == 1:
		print('0')
	else:
		traverser = traversal.index(end)
		while traverser != 0:
			traverser = traversal.index(origin[traverser])
			ans += 1
		print(ans)

def bfs(adjacency, start, end):
	(st, visited, origin, flag) = (queue.Queue(), [start], [start], 1)
	st.put(start)
	while not st.empty():
		process = st.get()
		for i in range(len(adjacency[process])):
			if adjacency[process][i] and i not in visited:
				visited.append(i)
				st.put(i)
				origin.append(process)
		if end in visited:
			break
	return [visited, origin]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	adjacency = []
	for _ in range(n):
		s = str(input())
		adjacency.append([int(s[i]) if abs(len(adjacency) - i) <= k else 0 for i in range(len(s))])
	solve_under_the_tunnels(adjacency, n - 1)


import asyncio
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list()
	for i in range(n):
		a.append(input())
	c = []
	for i in range(n):
		b = []
		for j in range(n):
			if j >= i - k and j <= i + k:
				b.append(a[i][j])
			else:
				b.append('0')
		c.append(b)
	src = 0
	q = []
	q.append(src)
	dist = [0] * n
	dist[src] = 0
	visited = [0] * n
	visited[src] = 1
	while len(q) != 0:
		u = q.pop(0)
		for v in range(n):
			if c[u][v] == '1' and visited[v] == 0:
				q.append(v)
				visited[v] = 1
				dist[v] = dist[u] + 1
	if dist[n - 1] == 0:
		print('-1')
	else:
		print(dist[n - 1])


t = int(input())
while t > 0:
	(n, k) = list(map(int, input().split()))
	st = []
	for i in range(n):
		st.append(input())
	q = [0]
	dist = [-1] * n
	while len(q) > 0:
		pos = q.pop(0)
		for i in range(max(0, pos - k), min(n, pos + k + 1)):
			if st[pos][i] == '1' and dist[i] == -1:
				q.append(i)
				dist[i] = dist[pos] + 1
	print(dist[n - 1])
	t -= 1


def BFS(graph, src, dest, n, k):
	queue = []
	visited = [False] * n
	dist = [float('inf')] * n
	queue.append(src)
	visited[src] = True
	dist[src] = 0
	while queue:
		i = queue.pop(0)
		for j in graph[i]:
			if visited[j] != True and abs(i - j) <= k:
				visited[j] = True
				queue.append(j)
				dist[j] = dist[i] + 1
				if j == dest:
					return dist[j]
	return -1
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	graph = []
	for i in range(n):
		graph.append([])
		s = input()
		for j in range(len(s)):
			if s[j] == '1':
				graph[i].append(j)
	ans = BFS(graph, 0, n - 1, n, k)
	print(ans)


from collections import deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = []
	for i in range(n):
		lst.append(input())
	begin = (0, 0)
	dq = deque()
	dq.append(begin)
	visit = [-1] * n
	visit[0] = 0
	flag = False
	while len(dq):
		(a, b) = dq.pop()
		for i in range(n):
			if lst[a][i] == '1' and abs(a - i) <= k and (visit[i] > b + 1 or visit[i] == -1):
				dq.append((i, b + 1))
				visit[i] = b + 1
	print(visit[n - 1])


path = {1: 0}

def BFS_short_path(l, fr0m, t0):
	q = []
	dic = {}
	q.append(fr0m)
	boo = False
	dic[fr0m] = 0
	while len(q) != 0:
		s = q.pop(0)
		for j in l[s]:
			if j not in dic.keys():
				q.append(j)
				dic[j] = dic[s] + 1
				if j == t0:
					boo = True
		if boo:
			break
	c = dic[t0] if t0 in dic.keys() else -1
	print(c)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	dic = {}
	for i in range(1, n + 1):
		a = input()
		t = []
		for j in range(i - k, i + k + 1):
			if j < 1 or j > n:
				continue
			if a[j - 1] == '1':
				t.append(j)
		dic[i] = t
	BFS_short_path(dic, 1, n)


def neighbours(a):
	list1 = []
	for i in range(n):
		if adj[a][i] == 1:
			list1.append(i)
	return list1
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	steps = [0] * n
	for i in range(n):
		steps[i] = input()
	adj = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			elif abs(i - j) > k:
				continue
			elif steps[i][j] == '1':
				adj[i][j] = 1
	dis = [-1] * n
	dis[0] = 0
	queue = []
	queue.append(0)
	while len(queue) != 0:
		node = queue.pop(0)
		for i in neighbours(node):
			if dis[i] == -1:
				dis[i] = dis[node] + 1
				queue.append(i)
	print(dis[-1])


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	g = defaultdict(list)
	for i in range(n):
		for j in range(max(0, i - k), min(n, i + k + 1)):
			if i != j and l[i][j] == '1':
				g[i].append(j)
	vis = [0] * n
	dist = [0] * n
	q = [0]
	vis[0] = 1
	while q:
		no = q[0]
		del q[0]
		for i in g[no]:
			if vis[i] == 0:
				q.append(i)
				vis[i] = 1
				dist[i] = dist[no] + 1
	if dist[n - 1] == 0:
		print('-1')
	else:
		print(dist[n - 1])


from collections import defaultdict, deque

def addEdge(graph, u, v):
	graph[u].append(v)

def generate_edges(graph):
	edges = []
	for node in graph:
		for neighbour in graph[node]:
			edges.append((node, neighbour))
	return edges

def bfs2(graph, start, goal):
	if start == goal:
		return [start]
	visited = {start}
	queue = deque([(start, [])])
	while queue:
		(current, path) = queue.popleft()
		visited.add(current)
		for neighbor in graph[current]:
			if neighbor == goal:
				return path + [current, neighbor]
			if neighbor in visited:
				continue
			queue.append((neighbor, path + [current]))
			visited.add(neighbor)
	return None
t = int(input())
for _ in range(t):
	graph = defaultdict(list)
	(n, k) = map(int, input().split())
	for i in range(n):
		string = input()
		for j in range(1, k + 1):
			if i + j < n:
				if string[i + j] == '1':
					addEdge(graph, i, i + j)
			if i - j >= 0:
				if string[i - j] == '1':
					addEdge(graph, i, i - j)
	path = bfs2(graph, 0, n - 1)
	if path:
		print(len(path) - 1)
	else:
		print(-1)


from collections import deque
for _ in range(int(input())):
	(N, K) = map(int, input().split(' '))
	A = [[] for i in range(N)]
	for i in range(N):
		S = input()
		for j in range(max(0, i - K), min(N, i + K + 1)):
			if S[j] == '1':
				A[i].append(j)
	myqueue = deque()
	myqueue.append(0)
	dis = [-1 for i in range(N)]
	dis[0] = 0
	mark = [-1 for i in range(N)]
	mark[0] = 1
	while len(myqueue) != 0:
		x = myqueue.popleft()
		for i in A[x]:
			if mark[i] == -1:
				mark[i] = 1
				dis[i] = dis[x] + 1
				myqueue.append(i)
			if i == N - 1:
				myqueue = []
				break
		else:
			continue
	print(dis[N - 1])


min = [10000000]
dp = []

def dfs(graph, x, count, dp):
	if x == N - 1:
		if min[0] > count:
			min[0] = count
		return
	else:
		count += 1
		dp[x] = 1
		for i in graph[x]:
			if dp[i] == 0:
				dfs(graph, i, count, dp[:])

def BFS(graph, src, dest, v, k):
	queue = []
	visited = [False] * v
	dist = [float('inf')] * v
	pred = [-1] * v
	visited[src] = True
	dist[src] = 0
	queue.append(src)
	while queue:
		u = queue.pop(0)
		for i in graph[u]:
			if visited[i] == False and abs(i - u) <= k:
				visited[i] = True
				dist[i] = dist[u] + 1
				pred[i] = u
				queue.append(i)
				if i == dest:
					return dist[i]
	return -1
t = int(input())
for _ in range(t):
	(N, K) = map(int, input().split())
	S = []
	min = [10000000]
	dp = [0] * N
	graph = list(map(lambda x: [], [i for i in range(N)]))
	for i in range(N):
		s = input()
		j = i - 1
		while i - j <= K and j >= 0:
			if s[j] == '1':
				graph[i].append(j)
			j -= 1
		j = i + 1
		while abs(i - j) <= K and abs(j) < N:
			if s[j] == '1':
				graph[i].append(j)
			j += 1
	print(BFS(graph, 0, N - 1, N, K))


from collections import deque
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = []
	for i in range(N):
		S.append(input())
	jumps = [0] * N
	queue = deque()
	queue.append(0)
	while len(queue) > 0:
		i = queue.popleft()
		for k in range(1, K + 1):
			j = i + k
			if j < N and S[i][j] == '1':
				if jumps[j] == 0 or jumps[j] > jumps[i] + 1:
					jumps[j] = jumps[i] + 1
					queue.append(j)
			j = i - k
			if j >= 0 and S[i][j] == '1':
				if jumps[j] == 0 or jumps[j] > jumps[i] + 1:
					jumps[j] = jumps[i] + 1
					queue.append(j)
	if jumps[N - 1] == 0:
		print(-1)
	else:
		print(jumps[N - 1])


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = [input() for _ in range(N)]
	J = 0
	Q = {0}
	X = N - 1
	V = [1] + [0] * X
	while Q:
		if X in Q:
			print(J)
			break
		W = set()
		J += 1
		for P in Q:
			for I in range(max(0, P - K), min(P + K + 1, N)):
				if not V[I]:
					if S[P][I] == '1':
						W.add(I)
						V[I] = 1
		Q = W
	else:
		print(-1)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = [input() for _ in range(N)]
	J = 0
	Q = [0]
	V = [True] + [False] * (N - 1)
	while len(Q) > 0:
		if N - 1 in Q:
			print(J)
			break
		W = []
		J += 1
		for P in Q:
			for I in range(max(0, P - K), min(P + K + 1, N)):
				if S[P][I] == '1' and (not V[I]):
					W += (I,)
					V[I] = True
		Q = W
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	a = []
	for _ in range(n):
		a.append(list(input()))
	visited = [False] * n
	q = []
	q.append(0)
	visited[0] = True
	mapp = {}
	mapp[0] = 0
	while len(q) != 0:
		front = q[0]
		for i in range(front + 1, min(front + k, n - 1) + 1):
			if not visited[i] and a[front][i] == '1':
				visited[i] = True
				q.append(i)
				mapp[i] = mapp[front] + 1
		for i in range(max(front - k, 0), front):
			if not visited[i] and a[front][i] == '1':
				visited[i] = True
				q.append(i)
				mapp[i] = mapp[front] + 1
		if visited[n - 1]:
			break
		q.pop(0)
	if visited[n - 1]:
		print(mapp[n - 1])
	else:
		print(-1)


from collections import deque
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	arr = []
	for i in range(n):
		arr.append(input())
	adj_list = []
	for i in range(n):
		temp = []
		adj_list.append(temp)
	for i in range(n):
		for j in range(i - k, i + k + 1):
			if j >= 0 and j < n:
				if arr[i][j] == '1' and i != j:
					adj_list[i].append(j)
	visited = [False] * n
	raj = deque()
	raj.append(0)
	flg = 0
	while len(raj) != 0:
		x = raj.popleft()
		if x == n - 1:
			flg = 1
			break
		for i in adj_list[x]:
			if visited[i] == False:
				raj.append(i)
				visited[i] = True
	if flg == 0:
		print(-1)
	else:
		visited = [False] * n
		raj = deque()
		raj.append((0, 0))
		flg = 0
		while len(raj) != 0:
			x = raj.popleft()
			if x[0] == n - 1:
				flg = x
				break
			for i in adj_list[x[0]]:
				if visited[i] == False:
					raj.append((i, x[1] + 1))
					visited[i] = True
		print(flg[1])


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = []
	for I in range(N):
		S += (input(),)
	F = []
	for I in range(N):
		Z = []
		for J in range(I - K, I + K + 1):
			if -1 < J < N:
				if I != J and S[I][J] == '1':
					Z += (J,)
		F += (Z,)
	X = [False] * N
	X[0] = True
	J = 0
	Y = [0]
	while len(Y) > 0:
		if N - 1 in Y:
			print(J)
			break
		Q = []
		J += 1
		for V in Y:
			for L in F[V]:
				if not X[L]:
					Q.append(L)
					X[L] = True
		Y = Q
	else:
		print(-1)


t = int(input())
from collections import defaultdict

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def BFS(self, s):
		visited = [False] * len(self.graph)
		queue = []
		queue.append((s, 0))
		visited[s] = True
		l = []
		while queue:
			s = queue.pop(0)
			for i in self.graph[s[0]]:
				if visited[i] == False:
					queue.append((i, s[1] + 1))
					l.append((i, s[1] + 1))
					visited[i] = True
		return l
for _ in range(t):
	g = Graph()
	(n, k) = list(map(int, input().rstrip().split()))
	for i in range(n):
		s = input()
		for j in range(max(0, i - k), min(n, i + k + 1)):
			if s[j] == '1':
				g.addEdge(i, j)
	count = -1
	for i in g.BFS(0):
		if i[0] == n - 1:
			count = i[1]
			break
	print(count)


t = int(input())
for _ in range(t):
	str = []
	(n, k) = [int(i) for i in input().split(' ')]
	arr = [[] for j in range(n)]
	for i in range(n):
		str = input()
		for j in range(max(i - k, 0), min(n, i + k + 1)):
			if str[j] == '1':
				arr[i].append(j)
	dist = [100000000 for i in range(n)]
	dist[0] = 0
	list = [0]
	check = True
	while len(list) > 0:
		for j in arr[list[0]]:
			if dist[j] == 100000000:
				dist[j] = dist[list[0]] + 1
				list.append(j)
				if j == n - 1:
					check = False
		list = list[1:]
	if dist[n - 1] == 100000000:
		dist[n - 1] = -1
	print(dist[n - 1])


t = input()
t = int(t)
for i in range(0, t):
	(n, k) = [int(e) for e in input().split(' ')]
	switch_array = []
	adjaceny_list = []
	for j in range(0, n):
		switch_array.append(input())
		j_adj_list = []
		for l in range(max(j - k, 0), min(j + k, n - 1) + 1):
			if l != j and switch_array[j][l] == '1':
				j_adj_list.append(l)
		adjaceny_list.append(j_adj_list)
	bfs_queue = []
	if n - 1 == 0:
		print(0)
	else:
		bfs_queue.append([0, 0])
		visited_dict = {}
		result = -1
		while len(bfs_queue) > 0 and result == -1:
			curr_node = bfs_queue.pop(0)
			if curr_node[0] not in visited_dict:
				visited_dict[curr_node[0]] = 1
				for adj_node in adjaceny_list[curr_node[0]]:
					if adj_node not in visited_dict:
						if adj_node == n - 1:
							result = curr_node[1] + 1
							break
						bfs_queue.append([adj_node, curr_node[1] + 1])
		print(result)


from collections import deque
mm = 100000000000
t = int(input())

def mind(dis, vis):
	mi = mm
	mii = -1
	for i in range(n):
		if dis[i] < mi and vis[i] == -1:
			mi = dis[i]
			mii = i
	return mii
while t:
	l = []
	(n, k) = map(int, input().split())
	for i in range(n):
		ll = list(map(int, input().strip()))
		l.append(ll)
	dis = [mm] * n
	dis[0] = 0
	q = deque([0])
	while q:
		u = q.pop()
		for i in range(n):
			if abs(u - i) <= k and l[u][i]:
				if dis[i] > 1 + dis[u]:
					dis[i] = 1 + dis[u]
					q.appendleft(i)
	if dis[n - 1] == mm:
		print(-1)
	else:
		print(dis[n - 1])
	t -= 1


class Graph:

	def __init__(self):
		self.graph = dict()

	def addEdge(self, arr, n):
		for i in range(0, n):
			for j in range(0, n):
				if arr[i][j] == '1':
					if i in self.graph.keys():
						self.graph[i].append(j)
					else:
						self.graph[i] = [j]

	def dfs(self, n, k):
		queue = []
		src = 0
		visited = [0 for i in range(n)]
		queue.append(src)
		visited[src] = 1
		dist = [0] * n
		while len(queue) != 0:
			ele = queue.pop(0)
			for nei in self.graph[ele]:
				if visited[nei] == 0 and nei - ele <= k:
					queue.append(nei)
					dist[nei] = dist[ele] + 1
					visited[nei] = 1
		return dist[n - 1]
test = int(input())
while test != 0:
	(n, k) = map(int, input().split())
	arr = []
	temp = n
	while temp != 0:
		str1 = input()
		b = list(str1)
		arr.append(b)
		temp -= 1
	obj = Graph()
	obj.addEdge(arr, n)
	ans = obj.dfs(n, k)
	if ans == 0:
		print(-1)
	else:
		print(ans)
	test -= 1


for t in range(int(input())):
	(n, k) = map(int, input().split())
	m = {}
	for i in range(n):
		s = list(input())
		m[i] = []
		for j in range(len(s)):
			if i != j:
				if s[j] == '1':
					m[i].append(j)
	queue = []
	queue.append(0)
	visited = [False] * n
	visited[0] = True
	dist = [float('inf')] * n
	dist[0] = 0
	flag = 0
	while queue:
		ele = queue.pop(0)
		data = m.get(ele)
		for i in data:
			if visited[i] == False and abs(i - ele) <= k:
				visited[i] = True
				dist[i] = dist[ele] + 1
				queue.append(i)
				if i == n - 1:
					flag = 1
					break
	if flag == 0:
		print(-1)
	else:
		print(dist[-1])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	f = float('inf')
	dp = [f] * n
	dp[0] = 0
	vis = [0] * n
	q = [0]
	s = []
	for i in range(n):
		t = input()
		s.append(t)
	while len(q) > 0:
		curr = q.pop(0)
		if vis[curr] == 1:
			continue
		for i in range(max(curr - k, 0), min(n, curr + k + 1)):
			if i == curr:
				continue
			elif s[curr][i] == '1' and vis[i] == 0:
				dp[i] = min(dp[i], dp[curr] + 1)
				q.append(i)
		vis[curr] = 1
	if dp[-1] == f:
		dp[-1] = -1
	print(dp[-1])


from collections import deque

def main():
	t = int(input())
	for __ in range(t):
		(N, K) = map(int, input().split())
		path = {}
		for i in range(1, N + 1):
			path[i] = []
		i = 1
		while i <= N:
			s = input()
			for j in range(1, N + 1):
				if s[j - 1] == '1':
					path[i].append(j)
			i += 1
		print(bfs(path, K, N))

def bfs(path, K, N):
	visited = [False] * N
	dist = {}
	dist[1] = 0
	q = deque()
	parent = 1
	q.append((1, path[1]))
	visited[0] = True
	while q:
		(parent, v) = q[0]
		q.popleft()
		for i in v:
			if i == N and N - parent <= K:
				return dist[parent] + 1
			elif abs(i - parent) <= K and (not visited[i - 1]):
				q.append((i, path[i]))
				visited[i - 1] = True
				dist[i] = dist[parent] + 1
	return -1
main()


import sys
from collections import defaultdict, Counter

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

def mapi():
	return map(int, input().split())

def print(arg, *argv, end=None):
	sys.stdout.write(str(arg))
	for i in argv:
		sys.stdout.write(' ' + str(i))
	sys.stdout.write(end) if end else sys.stdout.write('\n')

def solve():
	t = 1
	t = int(input())
	while t:
		t -= 1
		(n, k) = mapi()
		g = defaultdict(list)
		for i in range(n):
			s = input()
			for j in range(n):
				if s[j] == '1' and abs(i - j) <= k:
					g[i].append(j)
		q = []
		vis = {}
		q.append(0)
		vis[0] = 1
		while len(q) != 0:
			tmp = q.pop(0)
			for item in g[tmp]:
				if item not in vis:
					vis[item] = vis[tmp] + 1
					q.append(item)
					if item == n - 1:
						q = []
						break
		if n - 1 not in vis:
			print(-1)
		else:
			print(vis[n - 1] - 1)
solve()


from queue import Queue
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	graph = {}
	visited = [False] * (n + 1)
	distance = [-1] * (n + 1)
	distance[1] = 0
	visited[1] = True
	q = Queue()
	q.put(1)
	for i in range(1, n + 1):
		graph[i] = []
	for i in range(1, n + 1):
		s = input()
		st = max(0, i - k - 1)
		end = min(n, i + k)
		for x in range(st, end):
			if s[x] == '1':
				graph[i].append(x + 1)
	while q.empty() == False:
		u = q.get()
		for i in graph[u]:
			if visited[i] == False:
				visited[i] = True
				distance[i] = distance[u] + 1
				q.put(i)
	print(distance[n])


T = int(input())
while T > 0:
	(N, K) = map(int, input().split())
	l = []
	for _ in range(N):
		S = input()
		l.append(S)
	d = [0 for i in range(N)]
	stack = []
	visited = [False for i in range(N)]
	stack.append(0)
	while stack != []:
		i = stack.pop()
		j = max(0, i - K)
		while j < N and j <= i + K:
			if i == j:
				j += 1
				continue
			elif l[i][j] == '1' and d[j] != 0:
				if d[j] > d[i] + 1:
					stack.append(j)
				d[j] = min(d[j], d[i] + 1)
			elif l[i][j] == '1' and d[j] == 0:
				visited[j] == True
				d[j] = d[i] + 1
				stack.append(j)
			j += 1
	if d[-1] == 0:
		print(-1)
	else:
		print(d[-1])
	T -= 1


import sys
sys.setrecursionlimit(100000)

def fun(ans, k, stack):
	if len(stack) == 0:
		return ans
	i = stack.pop()
	st = max(i - k, 0)
	end = min(n - 1, i + k)
	for j in range(st, end + 1):
		if s[j][i] == '1' and i != j:
			if ans[j] > ans[i] + 1:
				stack.append(j)
				ans[j] = min(ans[j], ans[i] + 1)
	return fun(ans, k, stack)
for t in range(int(input())):
	(n, k) = [int(j) for j in input().split()]
	s = []
	for i in range(n):
		s.append(input())
	ans = [10 ** 10] * (n - 1)
	ans.append(0)
	ans = fun(ans, k, [n - 1])
	if ans[0] != 10 ** 10:
		print(ans[0])
	else:
		print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = []
	for _ in range(n):
		s.append(input())
	depth = 0
	visited = []
	if s[-1][n - 1] == '1':
		oldctiles = [n - 1]
		while True:
			newctiles = []
			depth += 1
			for step in range(1, k + 1):
				for ctile in set(oldctiles):
					visited.append(ctile)
					if ctile - step >= 0:
						if s[ctile - step][ctile - step] == '1' and s[ctile - step][ctile] == '1':
							tile = ctile - step
							newctiles.append(tile)
						else:
							pass
					if ctile + step <= n - 1:
						if s[ctile + step][ctile + step] == '1' and s[ctile + step][ctile] == '1':
							tile = ctile + step
							newctiles.append(tile)
						else:
							pass
			if 0 in newctiles:
				print(depth)
				break
			if newctiles == []:
				print(-1)
				break
			if oldctiles == set(newctiles):
				print(-1)
				break
			if set(newctiles).issubset(set(visited)):
				print(-1)
				break
			oldctiles = newctiles[:]
	else:
		print(-1)


from sys import maxsize as INT_MAX
from collections import deque
V = 1001

class node:

	def __init__(self, to, weight):
		self.to = to
		self.weight = weight
edges = [0] * V
for i in range(V):
	edges[i] = []

def zeroOneBFS(src: int, dist):
	for i in range(V):
		dist[i] = INT_MAX
	Q = deque()
	dist[src] = 0
	Q.append(src)
	while Q:
		v = Q[0]
		Q.popleft()
		for i in range(len(edges[v])):
			if dist[edges[v][i].to] > dist[v] + edges[v][i].weight:
				dist[edges[v][i].to] = dist[v] + edges[v][i].weight
				if edges[v][i].weight == 0:
					Q.appendleft(edges[v][i].to)
				else:
					Q.append(edges[v][i].to)

def addEdge(u: int, v: int, wt: int):
	edges[u].append(node(v, wt))
	edges[u].append(node(v, wt))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	for i in range(n):
		s = input()
		for j in range(max(0, i - k), min(n, i + k + 1)):
			if s[j] == '1':
				addEdge(i, j, 1)
	src = 0
	dist = [0] * V
	zeroOneBFS(src, dist)
	ans = dist[n - 1]
	if ans == 9223372036854775807:
		print(-1)
		for i in range(V):
			edges[i] = []
	else:
		print(ans)
		for i in range(V):
			edges[i] = []


import queue

def minEdgeBFS(edges, u, v, n):
	visited = [0] * n
	distance = [0] * n
	Q = queue.Queue()
	distance[u] = 0
	Q.put(u)
	visited[u] = True
	while not Q.empty():
		x = Q.get()
		for i in range(len(edges[x])):
			if visited[edges[x][i]]:
				continue
			distance[edges[x][i]] = distance[x] + 1
			Q.put(edges[x][i])
			visited[edges[x][i]] = 1
	return distance[v]
for test_case in range(int(input())):
	(N, K) = map(int, input().split())
	array = []
	for i in range(N):
		array.append([])
	for i in range(N):
		pepe = input()
		a = min(i, K)
		b = min(N, i + K + 1)
		for l in range(i - a, b):
			if pepe[l] == '1' and l != i:
				array[i].append(l)
	answer = minEdgeBFS(array, 0, N - 1, N)
	if answer == 0:
		print(-1)
	else:
		print(answer)


from copy import deepcopy
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	s = [''] * n
	for i in range(n):
		s[i] = input()
	mat = [float('inf') for _ in range(n)]
	change = True
	while True:
		matOld = deepcopy(mat)
		for i in range(n):
			for j in range(-k, k + 1):
				if i + j < n - 1 and i + j > 0 and (s[i][i + j] == '1'):
					mat[i] = min(mat[i], mat[i + j] + 1)
				if i + j == n - 1 and s[i][i + j] == '1':
					mat[i] = 1
		if matOld == mat:
			break
	if mat[0] == float('inf'):
		print(-1)
	else:
		print(mat[0])


from collections import defaultdict
for x in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	for x in range(n):
		l.append(input())
	l1 = [n - 1]
	c = 0
	k1 = 0
	visited = defaultdict(int)
	while 0 not in l1 and len(l1) != 0:
		l2 = []
		for x in l1:
			for y in range(n):
				if l[y][x] == '1' and abs(y - x) <= k and (y != x) and (visited[y] != 1):
					l2.append(y)
					visited[y] = 1
		l1 = l2.copy()
		c += 1
	if l1 == []:
		print(-1)
	else:
		print(c)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		s = input()
		a.append(s)
	re = []
	for i in range(n):
		f = []
		for j in range(n):
			if i == j:
				continue
			if a[i][j] == '1':
				if abs(i - j) <= k:
					f.append(j)
		re.append(f)
	res = set()
	c = 0
	flag = 0
	vis = [0 for i in range(n)]
	queue = [0]
	while len(queue) != 0:
		c += 1
		temp = []
		for i in range(len(queue) - 1, -1, -1):
			if vis[queue[i]] == 0:
				vis[queue[i]] = 1
				for k in range(len(re[queue[i]])):
					res.add(re[queue[i]][k])
					if vis[re[queue[i]][k]]:
						continue
					temp.append(re[queue[i]][k])
		queue = temp
		if n - 1 in res:
			flag = 1
			break
	if flag == 0:
		print(-1)
	else:
		print(c)


t = int(input())
while t > 0:
	(N, K) = [int(c) for c in input().split(' ')]
	strings = []
	for i in range(N):
		strings.append(input().strip())
	min_steps = [10 ** 10 for i in range(N)]
	min_steps[0] = 0
	for p in range(100):
		for i in range(1, N):
			for j in range(i - K, i + K + 1):
				if j >= 0 and j < N and (j != i) and (strings[j][i] == '1'):
					min_steps[i] = min(min_steps[i], min_steps[j] + 1)
	if min_steps[N - 1] >= 10 ** 10:
		print(-1)
	else:
		print(min_steps[N - 1])
	t -= 1


def BFS(gph, s, d, v, pred, dist):
	queue = []
	visited = [False] * v
	visited[s] = True
	dist[s] = 0
	queue.append(s)
	while len(queue) != 0:
		u = queue[0]
		del queue[0]
		for i in range(len(gph[u])):
			if visited[gph[u][i]] == False:
				visited[gph[u][i]] = True
				dist[gph[u][i]] = dist[u] + 1
				pred[gph[u][i]] = u
				queue.append(gph[u][i])
				if gph[u][i] == d:
					return True
	return False

def printShortestDistance(gph, s, d, v):
	pred = [-1] * v
	dist = [7 + 10 ** 9] * v
	if BFS(gph, s, d, v, pred, dist) == False:
		print(-1)
		return
	path = []
	crawl = d
	path.append(crawl)
	while pred[crawl] != -1:
		path.append(pred[crawl])
		crawl = pred[crawl]
	print(dist[d])
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lis = []
	for i in range(n):
		lis.append(input())
	gph = dict()
	for i in range(n):
		gph[i] = []
	for i in range(n):
		for j in range(n):
			if i != j and abs(i - j) <= k and (lis[i][j] == '1'):
				gph[i].append(j)
	printShortestDistance(gph, 0, n - 1, n)


from sys import stdin, stdout
from collections import defaultdict
for t in range(int(input())):
	(N, K) = map(int, input().split())
	adj = defaultdict(list)
	terror = False
	for k in range(N):
		S = input()
		if S[k] == '0':
			terror = True
		m = max(0, k - K)
		M = min(N, k + K + 1)
		for h in range(m, k):
			if S[h] == '1':
				adj[k].append(h)
		for hb in range(k + 1, M):
			if S[hb] == '1':
				adj[k].append(hb)
	if terror == True:
		print('-1')
		continue
	seen = [0 for j in range(N)]
	seen[0] = 1
	start = [0]
	n = []
	parent = defaultdict(int)
	parent[0] = 0
	while True:
		next = []
		if len(start) == 0:
			break
		else:
			for item in start:
				AD = adj[item]
				for x in AD:
					if seen[x] == 0:
						next.append(x)
						parent[x] = start[0]
						seen[x] = 1
			start = next
	child = N - 1
	step = 0
	while child != 0:
		step += 1
		child = parent[child]
	if seen[N - 1] == 1:
		print(step)
	else:
		print('-1')


def recSolve(tiles, pos, k, visited, dist):
	if visited[pos] != -1 and dist >= visited[pos] or tiles[pos][pos] == '0':
		return
	visited[pos] = dist
	for i in range(max(0, pos - k), min(len(tiles), pos + k + 1)):
		if tiles[pos][i] != '0':
			recSolve(tiles, i, k, visited, dist + 1)
t = int(input())
while t != 0:
	(n, k) = list(map(int, input().split()))
	tiles = []
	for _ in range(n):
		tiles.append(input())
	visited = [-1 for _ in range(n)]
	recSolve(tiles, 0, k, visited, 0)
	print(visited[-1])
	t -= 1


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n').split(' ')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
for _ in range(val()):
	(n, k) = li()
	l = []
	for i in range(n):
		l.append(li3())
	dp = [float('inf') for i in range(n)]
	currleft = deque()
	currleft.append(0)
	visited = set([0])
	dp[0] = 0
	while len(currleft):
		i = currleft.popleft()
		for j in range(max(0, i - k), min(n, i + k + 1), 1):
			if l[i][j]:
				dp[j] = min(dp[j], dp[i] + 1)
				if j not in visited:
					currleft.append(j)
					visited.add(j)
	print(dp[-1] if dp[-1] != float('inf') else -1)


import sys
from collections import defaultdict
from math import inf
import heapq
input = sys.stdin.readline

def solve(n, k, arr):
	graph = defaultdict(set)
	for i in range(1, n + 1):
		for j in range(max(1, i - k), min(n + 1, i + k + 1)):
			if i != j:
				if arr[i - 1][j - 1] == '1':
					graph[i].add(j)
	for key in graph:
		graph[key] = list(graph[key])
	(start, end) = (1, n)
	heap = [(0, start)]
	visited = set()
	while heap:
		(u_dist, u) = heapq.heappop(heap)
		if u not in visited:
			visited.add(u)
			if u == end:
				return u_dist
			for v in graph[u]:
				if v not in visited:
					dist = u_dist + 1
					heapq.heappush(heap, (dist, v))
	return -1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [input() for i in range(n)]
	print(solve(n, k, arr))


import sys
import math

class Graph:

	def __init__(self, vertices):
		self.V = vertices
		self.graph = [[0 for column in range(vertices)] for row in range(vertices)]

	def printSolution(self, dist):
		for node in range(self.V):
			if self.V - 1 == node:
				if dist[node] == float('Inf'):
					print('-1')
				else:
					print(dist[node])

	def minDistance(self, dist, sptSet):
		min1 = float('Inf')
		min_index = 0
		for v in range(self.V):
			if dist[v] < min1 and sptSet[v] == False:
				min1 = dist[v]
				min_index = v
		return min_index

	def dijkstra(self, src):
		dist = [float('Inf')] * self.V
		dist[src] = 0
		sptSet = [False] * self.V
		for cout in range(self.V):
			u = self.minDistance(dist, sptSet)
			sptSet[u] = True
			for v in range(self.V):
				if self.graph[u][v] > 0 and sptSet[v] == False and (dist[v] > dist[u] + self.graph[u][v]):
					dist[v] = dist[u] + self.graph[u][v]
		self.printSolution(dist)
for t in range(int(input())):
	(n, k) = map(int, input().split(' '))
	arr = []
	for i in range(n):
		arr.append(input())
	g = Graph(n)
	g.graph = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(n):
			if j != i:
				if arr[i][j] == '1' and math.fabs(i - j) <= k:
					g.graph[i][j] = 1
	g.dijkstra(0)


def bfs(self, n):
	visited = [0] * (n + 1)
	visited[1] = 1
	queue = []
	queue.append(1)
	queue.append(None)
	bfs_list = []
	count = 0
	while len(queue):
		current = queue.pop(0)
		if current == n:
			bfs_list.append(current)
			return count
		if current == None:
			count += 1
			if len(queue):
				queue.append(None)
		else:
			bfs_list.append(current)
			for node in d[current]:
				if not visited[node]:
					queue.append(node)
					visited[node] = 1
	return -1
tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	d = {}
	for i in range(1, n + 1):
		s = input()
		d[i] = []
		for (j, kl) in enumerate(s):
			if j + 1 != i and kl != '0' and (abs(j + 1 - i) <= k):
				d[i].append(j + 1)
	print(bfs(d, n))