Given a binary matrix M with R rows and C columns, where each element of the matrix will be 0 or 1. Find the largest square that can be formed with center (i, j) and contains atmost K 1s. There are Q queries, a single query has two integers denoting the centre (i,j) of the square.
 
Example 1:
Input:
R = 4, C = 5
M = {{1, 0, 1, 0, 0} 
     {1, 0, 1, 1, 1} 
     {1, 1, 1, 1, 1} 
     {1, 0, 0, 1, 0}}
K = 9, Q = 1
q_i[] = {1}
q_j[] = {2}
Output:
3
Explanation:
Maximum length square with center
at (1, 2) that can be formed is of
3 length from (0, 1) to (2, 3).
Example 2:
Input:
R = 3, C = 3
M = {{1, 1, 1} 
     {1, 1, 1} 
     {1, 1, 1}}
K = 9, Q = 2
q_i[] = {1, 2}
q_j[] = {1, 2}
Output :
3 1
Your Task:  
You don't need to read input or print anything. Your task is to complete the function largestSquare() which takes 2 integers R, and C followed by a list of lists M denoting the binary matrix and then three integers i,j, and K as input and returns a list of integers denting the largest Square possible for each query.
Expected Time Complexity: O(R*C + Q*log(MIN_DIST)),  where MIN_DIST is the minimum distance of the center from the edges of the matrix where MIN_DIST is the minimum distance of the center from the edges of the matrix.
Expected Auxiliary Space: O(R*C)
Constraints:
1 ≤ R,C ≤ 500
1 ≤ Q ≤ 10^{4}
0 ≤ K ≤ R*C
0 ≤ i < R
0 ≤ j < C

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Complete search

Dynamic programming

Divide and conquer

Matrices

Data structures

Starter code: #User function Template for python3



class Solution:

    def largestSquare(self, M, R, C, K, Q, q_i, q_j):

        # code here 

Solutions:
class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		for i in range(1, R):
			M[i][0] += M[i - 1][0]
		for i in range(1, C):
			M[0][i] += M[0][i - 1]
		for i in range(1, R):
			for j in range(1, C):
				M[i][j] = M[i - 1][j] + M[i][j - 1] - M[i - 1][j - 1] + M[i][j]
		res = [0] * Q
		for k in range(Q):
			i = q_i[k]
			j = q_j[k]
			p = 0
			while p + i < R and p + j < C and (i - p >= 0) and (j - p >= 0):
				(a, b, c) = (0, 0, 0)
				if j - p - 1 >= 0:
					a = M[i + p][j - p - 1]
				if i - p - 1 >= 0:
					b = M[i - p - 1][j + p]
				if j - p - 1 >= 0 and i - p - 1 >= 0:
					c = M[i - p - 1][j - p - 1]
				ans = M[i + p][j + p] - a - b + c
				if ans > K:
					break
				else:
					res[k] = 2 * p + 1
				p += 1
		return res


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		dp = [[0] * (C + 1) for _ in range(R + 1)]
		for i in range(R):
			for j in range(C):
				dp[i + 1][j + 1] = M[i][j] + dp[i + 1][j] + dp[i][j + 1] - dp[i][j]

		def sumarea(r2, c2, r1, c1):
			return dp[r2 + 1][c2 + 1] - dp[r2 + 1][c1] - dp[r1][c2 + 1] + dp[r1][c1]

		def query(i, j):
			ans = 0
			k = 0
			while True:
				(r1, c1) = (i - k, j - k)
				(r2, c2) = (i + k, j + k)
				if r1 < 0 or r2 >= R or c1 < 0 or (c2 >= C):
					break
				s = sumarea(r2, c2, r1, c1)
				if s > K:
					break
				ans = 2 * k + 1
				k += 1
			return ans
		return [query(i, j) for (i, j) in zip(q_i, q_j)]


class Prefix:

	def __init__(self, grid):
		self.numRows = len(grid)
		self.numCols = len(grid[0])
		self.prefix = [[0 for cell in range(self.numCols + 1)] for row in range(self.numRows + 1)]
		self.build(grid)

	def build(self, grid):
		for row in range(1, self.numRows + 1):
			for col in range(1, self.numCols + 1):
				self.prefix[row][col] = grid[row - 1][col - 1] + self.prefix[row - 1][col] + self.prefix[row][col - 1] - self.prefix[row - 1][col - 1]

	def calcRectangle(self, startRow, startCol, endRow, endCol):
		fullRec = self.prefix[endRow][endCol]
		topRec = self.prefix[startRow - 1][endCol]
		leftRec = self.prefix[endRow][startCol - 1]
		commonRec = self.prefix[startRow - 1][startCol - 1]
		recVal = fullRec - topRec - leftRec + commonRec
		return recVal

	def checkRec(self, startx, starty, endx, endy, ln, k):
		startx -= ln
		starty -= ln
		endx += ln
		endy += ln
		if startx > 0 and starty > 0 and (endx <= self.numRows) and (endy <= self.numCols):
			val = self.calcRectangle(startx, starty, endx, endy)
			return val <= k
		else:
			return False

class Solution:

	def largestSquare(self, grid, numRows, numCols, k, q, q_i, q_j):
		res = []
		prefix = Prefix(grid)
		for (i, j) in zip(q_i, q_j):
			startx = endx = i + 1
			starty = endy = j + 1
			(lo, hi) = (0, min(i, j, numRows - i, numCols - j))
			ans = 0
			while lo <= hi:
				mid = (lo + hi) // 2
				if prefix.checkRec(startx, starty, endx, endy, mid, k):
					lo = mid + 1
					ans = 2 * mid + 1
				else:
					hi = mid - 1
			res.append(ans)
		return res


class Solution:

	def binarysearch(self, l, r, dp, k, i, j):
		if l <= r:
			mid = (l + r) // 2
			x1 = i - mid
			x2 = i + mid
			y1 = j - mid
			y2 = j + mid
			count = dp[x2][y2]
			if x1 > 0:
				count -= dp[x1 - 1][y2]
			if y1 > 0:
				count -= dp[x2][y1 - 1]
			if x1 > 0 and y1 > 0:
				count += dp[x1 - 1][y1 - 1]
			if count <= k:
				return self.binarysearch(mid + 1, r, dp, k, i, j)
			else:
				return self.binarysearch(l, mid - 1, dp, k, i, j)
		return r

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		dp = [[0 for j in range(C)] for i in range(R)]
		dp[0][0] = M[0][0]
		for i in range(1, C):
			dp[0][i] = dp[0][i - 1] + M[0][i]
		for j in range(1, R):
			dp[j][0] = dp[j - 1][0] + M[j][0]
		for i in range(1, R):
			for j in range(1, C):
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + M[i][j]
		lb = 0
		res = []
		for i in range(len(q_i)):
			up = min(q_i[i], q_j[i], R - q_i[i] - 1, C - q_j[i] - 1)
			res1 = self.binarysearch(lb, up, dp, K, q_i[i], q_j[i])
			if res1 == -1:
				res1 = 0
			else:
				res1 = 2 * res1 + 1
			res.append(res1)
		return res


class Solution:

	def largestSquare(self, A, R, C, K, Q, q_i, q_j):
		dp = [[0 for i in range(C)] for i in range(R)]
		dp[0][0] = A[0][0]
		for i in range(1, C):
			dp[0][i] = dp[0][i - 1] + A[0][i]
		for i in range(1, R):
			dp[i][0] = dp[i - 1][0] + A[i][0]
		for i in range(1, R):
			for j in range(1, C):
				dp[i][j] = A[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		res = []
		for i in range(Q):
			(x, y) = (q_i[i], q_j[i])
			d = min(x, y, R - x - 1, C - y - 1)
			ans = -1
			l = 0
			r = d
			while l <= r:
				mid = l + r >> 1
				x1 = x - mid
				x2 = x + mid
				y1 = y - mid
				y2 = y + mid
				c = dp[x2][y2]
				if x1 > 0:
					c -= dp[x1 - 1][y2]
				if y1 > 0:
					c -= dp[x2][y1 - 1]
				if x1 > 0 and y1 > 0:
					c += dp[x1 - 1][y1 - 1]
				if c <= K:
					ans = 2 * mid + 1
					l = mid + 1
				else:
					r = mid - 1
			if ans == -1:
				ans = 0
			res.append(ans)
		return res


class Solution:

	def getMinDistanceFromSides(self, R, C, x, y):
		return min(x - 0, y - 0, R - 1 - x, C - 1 - y)

	def getSubMatSum(self, prefix, x1, y1, x2, y2):
		left = prefix[x2][y1 - 1] if y1 > 0 else 0
		right = prefix[x1 - 1][y2] if x1 > 0 else 0
		top = prefix[x1 - 1][y1 - 1] if x1 > 0 and y1 > 0 else 0
		return prefix[x2][y2] - left - right + top

	def largestSquare(self, matrix, R, C, K, Q, q_i, q_j):
		prefix = [[0] * len(matrix[0]) for i in range(len(matrix))]
		prefix[0][0] = matrix[0][0]
		for i in range(1, len(matrix)):
			prefix[i][0] = prefix[i - 1][0] + matrix[i][0]
		for j in range(1, len(matrix[0])):
			prefix[0][j] = prefix[0][j - 1] + matrix[0][j]
		for i in range(1, len(matrix)):
			for j in range(1, len(matrix[0])):
				prefix[i][j] = matrix[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]
		result = []
		for i in range(Q):
			(x, y) = (q_i[i], q_j[i])
			(l, r) = (0, self.getMinDistanceFromSides(R, C, x, y))
			ans = 0
			while l <= r:
				mid = l + (r - l) // 2
				(x1, y1) = (x - mid, y - mid)
				(x2, y2) = (x + mid, y + mid)
				matSum = self.getSubMatSum(prefix, x1, y1, x2, y2)
				if matSum <= K:
					ans = max(ans, mid * 2 + 1)
					l = mid + 1
				else:
					r = mid - 1
			result.append(ans)
		return result


class Solution:

	def largestSquare(self, mat, m, n, K, query, q_i, q_j):
		countDP = [[0 for x in range(C)] for x in range(R)]
		countDP[0][0] = M[0][0]
		for i in range(1, R):
			countDP[i][0] = countDP[i - 1][0] + M[i][0]
		for j in range(1, C):
			countDP[0][j] = countDP[0][j - 1] + M[0][j]
		for i in range(1, R):
			for j in range(1, C):
				countDP[i][j] = M[i][j] + countDP[i - 1][j] + countDP[i][j - 1] - countDP[i - 1][j - 1]
		res = []
		for q in range(0, Q):
			i = q_i[q]
			j = q_j[q]
			min_dist = min(i, j, R - i - 1, C - j - 1)
			ans = -1
			l = 0
			u = min_dist
			while l <= u:
				mid = int((l + u) / 2)
				x1 = i - mid
				x2 = i + mid
				y1 = j - mid
				y2 = j + mid
				count = countDP[x2][y2]
				if x1 > 0:
					count -= countDP[x1 - 1][y2]
				if y1 > 0:
					count -= countDP[x2][y1 - 1]
				if x1 > 0 and y1 > 0:
					count += countDP[x1 - 1][y1 - 1]
				if count <= K:
					ans = 2 * mid + 1
					l = mid + 1
				else:
					u = mid - 1
			if ans == -1:
				ans = 0
			res.append(ans)
		return res


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		for i in range(1, R):
			M[i][0] += M[i - 1][0]
		for i in range(1, C):
			M[0][i] += M[0][i - 1]
		for i in range(1, R):
			for j in range(1, C):
				M[i][j] = M[i - 1][j] + M[i][j - 1] - M[i - 1][j - 1] + M[i][j]
		ans = [0] * Q
		for z in range(Q):
			i = q_i[z]
			j = q_j[z]
			l = 0
			while i + l < R and j + l < C and (i - l >= 0) and (j - l >= 0):
				(a, b, c) = (0, 0, 0)
				if j - 1 - l >= 0:
					a = M[i + l][j - 1 - l]
				if i - 1 - l >= 0:
					b = M[i - 1 - l][j + l]
				if j - 1 - l >= 0 and i - 1 - l >= 0:
					c = M[i - 1 - l][j - 1 - l]
				an = M[i + l][j + l] - a - b + c
				if an > K:
					break
				else:
					ans[z] = 2 * l + 1
				l += 1
		return ans


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		l1 = []
		l2 = [[0] * (C + 1) for _ in range(R + 1)]
		i = 1
		while i <= R:
			j = 1
			while j <= C:
				l2[i][j] = M[i - 1][j - 1] + l2[i - 1][j] + l2[i][j - 1] - l2[i - 1][j - 1]
				j += 1
			i += 1
		q = 0
		while q < Q:
			i = q_i[q]
			j = q_j[q]
			d = min(min(i, j), min(R - i - 1, C - j - 1))
			ans = 0
			l = 0
			h = d
			while l <= h:
				m = int((l + h) / 2)
				x1 = i - m
				y1 = j - m
				x2 = i + m
				y2 = j + m
				count = l2[x2 + 1][y2 + 1] - l2[x1][y2 + 1] - l2[x2 + 1][y1] + l2[x1][y1]
				if count <= K:
					ans = 2 * m + 1
					l = m + 1
				else:
					h = m - 1
			l1.append(ans)
			q += 1
		return l1


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):

		def check_range_sum(i, j, k):
			(r1, c1) = (i - k, j - k)
			(r2, c2) = (i + k, j + k)
			if r1 < 0 or c1 < 0 or r2 >= R or (c2 >= C):
				return K + 1
			return ps_mat[r2 + 1][c2 + 1] + ps_mat[r1][c1] - ps_mat[r2 + 1][c1] - ps_mat[r1][c2 + 1]
		ps_mat = [[0] * (C + 1) for _ in range(R + 1)]
		for i in range(R):
			for j in range(C):
				ps_mat[i + 1][j + 1] = M[i][j] + ps_mat[i][j + 1] + ps_mat[i + 1][j] - ps_mat[i][j]
		ans = []
		for (i, j) in zip(q_i, q_j):
			k = 0
			while check_range_sum(i, j, k) <= K:
				k += 1
			ans.append(2 * k - 1 if k else k)
		return ans


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		query_coordinates = zip(q_i, q_j)
		largest_sq = [0 for i in range(Q)]
		subarr_sum_mat = [[0 for j in range(C)] for i in range(R)]
		subarr_sum_mat[0][0] = M[0][0]
		for i in range(R):
			pref_sum = 0
			for j in range(C):
				pref_sum += M[i][j]
				subarr_sum_mat[i][j] = pref_sum
		for j in range(C):
			for i in range(1, R):
				subarr_sum_mat[i][j] += subarr_sum_mat[i - 1][j]
		query_num = 0
		for (qi, qj) in query_coordinates:
			if qi in {0, R - 1} or qj in {0, C - 1}:
				if M[qi][qj] <= K:
					largest_sq[query_num] = 1
			else:
				max_sq_size = 2 * min(qi, qj, R - qi - 1, C - qj - 1) + 1
				sq_size = 1
				sq_sum = M[qi][qj]
				while sq_size <= max_sq_size:
					top_lft_corner = (qi - sq_size // 2, qj - sq_size // 2)
					top_rt_corner = (qi - sq_size // 2, qj + sq_size // 2)
					bott_lft_corner = (qi + sq_size // 2, qj - sq_size // 2)
					bott_rt_corner = (qi + sq_size // 2, qj + sq_size // 2)
					tot_area = subarr_sum_mat[bott_rt_corner[0]][bott_rt_corner[1]]
					top_area = subarr_sum_mat[top_rt_corner[0] - 1][top_rt_corner[1]] if top_rt_corner[0] != 0 else 0
					left_area = subarr_sum_mat[bott_lft_corner[0]][bott_lft_corner[1] - 1] if bott_lft_corner[1] != 0 else 0
					corner_area = subarr_sum_mat[top_lft_corner[0] - 1][top_lft_corner[1] - 1] if top_lft_corner[0] != 0 and top_lft_corner[1] != 0 else 0
					sq_sum = tot_area - top_area - left_area + corner_area
					if sq_sum <= K:
						largest_sq[query_num] = sq_size
					else:
						break
					sq_size += 2
			query_num += 1
		return largest_sq


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		row = []
		rsum = 0
		for x in M[0]:
			rsum += x
			row += [rsum]
		grid = [row + [0]]
		for i in range(1, R):
			row = []
			rsum = 0
			for (j, x) in enumerate(M[i]):
				rsum += x
				row += [grid[i - 1][j] + rsum]
			grid += [row + [0]]
		grid += [[0] * (C + 1)]
		result = []
		for (ic, jc) in zip(q_i, q_j):
			rmax = min(ic + 1, R - ic, jc + 1, C - jc)
			for r in range(rmax, 0, -1):
				inside = grid[ic + r - 1][jc + r - 1] + grid[ic - r][jc - r]
				inside -= grid[ic - r][jc + r - 1] + grid[ic + r - 1][jc - r]
				if inside <= K:
					break
			else:
				r = 0
			result.append(0 if r < 1 else 2 * r - 1)
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(R, C) = map(int, input().split())
		M = []
		for i in range(R):
			temp = list(map(int, input().split()))
			M.append(temp)
		(K, Q) = list(map(int, input().split()))
		q_i = list(map(int, input().split()))
		q_j = list(map(int, input().split()))
		ob = Solution()
		res = ob.largestSquare(M, R, C, K, Q, q_i, q_j)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		for i in range(1, R):
			M[i][0] += M[i - 1][0]
		for i in range(1, C):
			M[0][i] += M[0][i - 1]
		for i in range(1, R):
			for j in range(1, C):
				M[i][j] = M[i - 1][j] + M[i][j - 1] - M[i - 1][j - 1] + M[i][j]
		res = [0] * Q
		for k in range(Q):
			i = q_i[k]
			j = q_j[k]
			p = 0
			while p + i < R and p + j < C and (i - p >= 0) and (j - p >= 0):
				(a, b, c) = (0, 0, 0)
				if j - p - 1 >= 0:
					a = M[i + p][j - p - 1]
				if i - p - 1 >= 0:
					b = M[i - p - 1][j + p]
				if j - p - 1 >= 0 and i - p - 1 >= 0:
					c = M[i - p - 1][j - p - 1]
				ans = M[i + p][j + p] - a - b + c
				if ans > K:
					break
				else:
					res[k] = 2 * p + 1
				p += 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(R, C) = map(int, input().split())
		M = []
		for i in range(R):
			temp = list(map(int, input().split()))
			M.append(temp)
		(K, Q) = list(map(int, input().split()))
		q_i = list(map(int, input().split()))
		q_j = list(map(int, input().split()))
		ob = Solution()
		res = ob.largestSquare(M, R, C, K, Q, q_i, q_j)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		myDP = [[0] * (C + 1) for i in range(R + 1)]
		for i in range(R):
			for j in range(C):
				myDP[i + 1][j + 1] = M[i][j] + myDP[i + 1][j] + myDP[i][j + 1] - myDP[i][j]

		def Sum(a2, b2, a1, b1):
			return myDP[a2 + 1][b2 + 1] - myDP[a2 + 1][b1] - myDP[a1][b2 + 1] + myDP[a1][b1]

		def Query(i, j):
			ans = 0
			k = 0
			while True:
				(r1, c1) = (i - k, j - k)
				(r2, c2) = (i + k, j + k)
				if r1 < 0 or r2 >= R or c1 < 0 or (c2 >= C):
					break
				s = Sum(r2, c2, r1, c1)
				if s > K:
					break
				ans = 2 * k + 1
				k += 1
			return ans
		return [Query(i, j) for (i, j) in zip(q_i, q_j)]


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		dp = [[0 for k in range(C)] for k in range(R)]
		dp[0][0] = M[0][0]
		for i in range(1, R):
			dp[i][0] = dp[i - 1][0] + M[i][0]
		for j in range(1, C):
			dp[0][j] = dp[0][j - 1] + M[0][j - 1]
		for i in range(1, R):
			for j in range(1, C):
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + M[i][j]
		result = []
		for q in range(Q):
			i = q_i[q]
			j = q_j[q]
			min_dist = min(i, j, R - 1 - i, C - 1 - j)
			l = 0
			u = min_dist
			ans = 0
			while l <= u:
				mid = (l + u) // 2
				x1 = i - mid
				y1 = j - mid
				x2 = i + mid
				y2 = j + mid
				count = dp[x2][y2]
				if x1 > 0:
					count -= dp[x1 - 1][y2]
				if y1 > 0:
					count -= dp[x2][y1 - 1]
				if x1 > 0 and y1 > 0:
					count += dp[x1 - 1][y1 - 1]
				if count <= K:
					ans = 2 * mid + 1
					l = mid + 1
				else:
					u = mid - 1
			result.append(ans)
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(R, C) = map(int, input().split())
		M = []
		for i in range(R):
			temp = list(map(int, input().split()))
			M.append(temp)
		(K, Q) = list(map(int, input().split()))
		q_i = list(map(int, input().split()))
		q_j = list(map(int, input().split()))
		ob = Solution()
		res = ob.largestSquare(M, R, C, K, Q, q_i, q_j)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		dp = [[0 for k in range(C)] for k in range(R)]
		dp[0][0] = M[0][0]
		for i in range(1, R):
			dp[i][0] = dp[i - 1][0] + M[i][0]
		for j in range(1, C):
			dp[0][j] = dp[0][j - 1] + M[0][j - 1]
		for i in range(1, R):
			for j in range(1, C):
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + M[i][j]
		result = []
		for q in range(Q):
			i = q_i[q]
			j = q_j[q]
			min_dist = min(i, j, R - 1 - i, C - 1 - j)
			l = 0
			u = min_dist
			ans = 0
			while l <= u:
				mid = (l + u) // 2
				x1 = i - mid
				y1 = j - mid
				x2 = i + mid
				y2 = j + mid
				count = dp[x2][y2]
				if x1 > 0:
					count -= dp[x1 - 1][y2]
				if y1 > 0:
					count -= dp[x2][y1 - 1]
				if x1 > 0 and y1 > 0:
					count += dp[x1 - 1][y1 - 1]
				if count <= K:
					ans = 2 * mid + 1
					l = mid + 1
				else:
					u = mid - 1
			result.append(ans)
		return result


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		dp = [[0] * (C + 1) for _ in range(R + 1)]
		for i in range(R):
			pres = 0
			for j in range(C):
				pres += M[i][j]
				dp[i + 1][j + 1] = pres + dp[i][j + 1]
		ans = []
		for (x, y) in zip(q_i, q_j):
			max_l = 1
			temp = M[x][y] <= K
			(x, y) = (x + 1, y + 1)
			i = 1
			while True:
				(x1, y1) = (x - i, y - i)
				(x2, y2) = (x + i, y + i)
				i += 1
				if 0 < x1 < R + 1 and 0 < y1 < C + 1 and (0 < x2 < R + 1) and (0 < y2 < C + 1):
					once = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]
					if once > K:
						break
					else:
						max_l += 2
				else:
					break
			if max_l == 1 and (not temp):
				max_l = 0
			ans.append(max_l)
		return ans


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		dp = [[0] * (C + 1) for _ in range(R + 1)]
		for i in range(R):
			for j in range(C):
				dp[i + 1][j + 1] = M[i][j] + dp[i + 1][j] + dp[i][j + 1] - dp[i][j]

		def sumarea(r2, c2, r1, c1):
			return dp[r2 + 1][c2 + 1] - dp[r2 + 1][c1] - dp[r1][c2 + 1] + dp[r1][c1]

		def query(i, j):
			ans = 0
			k = 0
			while True:
				(r1, c1) = (i - k, j - k)
				(r2, c2) = (i + k, j + k)
				if r1 < 0 or r2 >= R or c1 < 0 or (c2 >= C):
					break
				s = sumarea(r2, c2, r1, c1)
				if s > K:
					break
				ans = 2 * k + 1
				k += 1
			return ans
		return [query(i, j) for (i, j) in zip(q_i, q_j)]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(R, C) = map(int, input().split())
		M = []
		for i in range(R):
			temp = list(map(int, input().split()))
			M.append(temp)
		(K, Q) = list(map(int, input().split()))
		q_i = list(map(int, input().split()))
		q_j = list(map(int, input().split()))
		ob = Solution()
		res = ob.largestSquare(M, R, C, K, Q, q_i, q_j)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def largestSquare(self, matrix, R, C, K, Q, q_i, q_j):
		countDP = [[0 for x in range(C)] for x in range(R)]
		countDP[0][0] = matrix[0][0]
		final = []
		for i in range(1, R):
			countDP[i][0] = countDP[i - 1][0] + matrix[i][0]
		for j in range(1, C):
			countDP[0][j] = countDP[0][j - 1] + matrix[0][j]
		for i in range(1, R):
			for j in range(1, C):
				countDP[i][j] = matrix[i][j] + countDP[i - 1][j] + countDP[i][j - 1] - countDP[i - 1][j - 1]
		for q in range(0, Q):
			i = q_i[q]
			j = q_j[q]
			min_dist = min(i, j, R - i - 1, C - j - 1)
			ans = 0
			for k in range(0, min_dist + 1):
				x1 = i - k
				x2 = i + k
				y1 = j - k
				y2 = j + k
				count = countDP[x2][y2]
				if x1 > 0:
					count -= countDP[x1 - 1][y2]
				if y1 > 0:
					count -= countDP[x2][y1 - 1]
				if x1 > 0 and y1 > 0:
					count += countDP[x1 - 1][y1 - 1]
				if count > K:
					break
				ans = 2 * k + 1
			final.append(ans)
		return final


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		psum = [[0 for _ in range(C)] for _ in range(R)]
		psum[0][0] = M[0][0]
		for i in range(1, C):
			psum[0][i] = psum[0][i - 1] + M[0][i]
		for i in range(1, R):
			psum[i][0] = psum[i - 1][0] + M[i][0]
		for i in range(1, R):
			for j in range(1, C):
				psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + M[i][j]

		def get_square_sum(i, j, d):
			nonlocal psum
			res = psum[i + d][j + d]
			if i - d - 1 >= 0:
				res -= psum[i - d - 1][j + d]
			if j - d - 1 >= 0:
				res -= psum[i + d][j - d - 1]
			if i - d - 1 >= 0 and j - d - 1 >= 0:
				res += psum[i - d - 1][j - d - 1]
			return res
		res = []
		for ix in range(Q):
			(i, j) = (q_i[ix], q_j[ix])
			if M[i][j] > K:
				res.append(0)
				continue
			m_dist = min(i, j, R - i - 1, C - j - 1)
			(l, r) = (0, m_dist)
			while l < r:
				mid = (l + r) // 2
				sq_sum = get_square_sum(i, j, mid)
				if sq_sum > K:
					r = mid
				else:
					l = mid + 1
			sq_sum = get_square_sum(i, j, l)
			if sq_sum > K:
				l -= 1
			res.append(1 + 2 * l)
		return res


class Solution:

	def largestSquare(self, M, R, C, K, Q, q_i, q_j):
		total = [[0 for c in range(C)] for r in range(R)]
		total[0][0] = M[0][0]
		for i in range(1, C):
			total[0][i] = total[0][i - 1] + M[0][i]
		for j in range(1, R):
			total[j][0] = total[j - 1][0] + M[j][0]
		for i in range(1, R):
			for j in range(1, C):
				total[i][j] = M[i][j] + total[i - 1][j] + total[i][j - 1] - total[i - 1][j - 1]
		result = list()
		for (i, j) in zip(q_i, q_j):
			min_dist = min(i, j, R - i - 1, C - j - 1)
			for d in range(0, min_dist + 1):
				x1 = i - d
				x2 = i + d
				y1 = j - d
				y2 = j + d
				count = total[x2][y2]
				if x1 > 0:
					count -= total[x1 - 1][y2]
				if y1 > 0:
					count -= total[x2][y1 - 1]
				if x1 > 0 and y1 > 0:
					count += total[x1 - 1][y1 - 1]
				if count > K:
					d -= 1
					if d < 0:
						d = 0
					break
			if K == 0 and M[i][j] == 1:
				result.append(2 * d)
			else:
				result.append(2 * d + 1)
		return result


class Solution:

	def largestSquare(self, arr, m, n, k, q, q_i, q_j):

		def get_count(i1, j1, i2, j2):
			if i1 == 0 and j1 == 0:
				return count_arr[i2][j2]
			if i1 == 0:
				return count_arr[i2][j2] - count_arr[i2][j1 - 1]
			if j1 == 0:
				return count_arr[i2][j2] - count_arr[i1 - 1][j2]
			return count_arr[i2][j2] - count_arr[i2][j1 - 1] - count_arr[i1 - 1][j2] + count_arr[i1 - 1][j1 - 1]
		count_arr = [[0] * n for _ in range(m)]
		for i in range(m):
			sum1 = 0
			for j in range(n):
				sum1 += arr[i][j]
				count_arr[i][j] += sum1
		for j in range(n):
			sum1 = 0
			for i in range(1, m):
				count_arr[i][j] += count_arr[i - 1][j]
		ans_arr = []
		for (i, j) in zip(q_i, q_j):
			if not arr[i][j]:
				ans = 1
			elif k != 0:
				ans = 1
			else:
				ans = 0
			(i1, j1) = (i - 1, j - 1)
			(i2, j2) = (i + 1, j + 1)
			while i1 >= 0 and j1 >= 0 and (i2 < m) and (j2 < n):
				ones = get_count(i1, j1, i2, j2)
				if ones > k:
					break
				ans = max(ans, i2 - i1 + 1)
				i1 -= 1
				j1 -= 1
				i2 += 1
				j2 += 1
			ans_arr.append(ans)
		return ans_arr