while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x+dx[k], y+dy[k]
if 0<=nx<n and 0<=ny<n and b[x][y] > b[nx][ny]:
q.append((nx, ny))
check[nx][ny] = max(check[x][y]+1, check[nx][ny])
# 최대한 긴 등산로 만들기
# <규칙>
# 1. 등산로는 가장 높은 봉우리에서 시작
# 2. 등산로는 높은 지형 -> 낮은 지형으로 연결되어야 (4방향으로)
# (높이가 낮은 지형으로만 이동 가능 !!)
# 3. 딱 한 곳을 정해서 "최대 K만큼" 지형을 깍는 공사 할 수 있다.
# (1, 2, 3, ..., K) 만큼씩 깎는거 시도해볼 수 있음
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
T = int(input())
for test_case in range(1, T+1):
answer = -1
# 입력
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
## 가장 높은 봉우리 - 높이 먼저 구해두기
high_len = max([max(row) for row in a])
# 가장 긴 등산로를 찾는 함수
def go(b, high_len):
global answer
for i in range(n):
for j in range(n):
if b[i][j] == high_len:
q = deque([(i, j)])
check = [[-1]*n for _ in range(n)]
check[i][j] = 1
while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x+dx[k], y+dy[k]
if 0<=nx<n and 0<=ny<n and b[x][y] > b[nx][ny]:
q.append((nx, ny))
check[nx][ny] = max(check[x][y]+1, check[nx][ny])
# if check[nx][ny] == -1 or check[nx][ny] < (check[x][y] + 1): ###
# ###q.append((nx, ny))
# check[nx][ny] = (check[x][y] + 1)
# 최댓값 비교
max_depth = max([max(row) for row in check])
if answer < max_depth:
answer = max_depth
'''
# if (i, j) == (2, 4):
# print()
# print('#####', test_case, ' 번 째')
# print((i, j), high_len)
# print()
# for line in b:
# print(line)
# print()
# for line in check:
# print(line)
# print('결과 : ', answer)
'''
# return 없음
## (1) 1 ~ K 만큼 깎지 않고 탐색
go(a, high_len)
## (2) 1 ~ K 만큼 깍아보면서 탐색
for cut_len in range(1, k+1):
for i in range(n):
for j in range(n):
### (주의) 처음에 이거 넣었더니 조금 다른 답이 나오기도 함
### -> 결국, 시작점으로 선택하는 "가장 높은 봉우리" 외의 다른 봉우리는 필요하다면, 딱 1번 깍아볼 수 있음
'''
if a[i][j] == high_len:
continue
'''
copy = [row[:] for row in a]
copy[i][j] -= cut_len
go(copy, high_len)
print('#{0} {1}'.format(test_case, answer))
# 기본 제공코드는 임의 수정해도 관계 없습니다. 단, 입출력 포맷 주의
# 아래 표준 입출력 예제 필요시 참고하세요.
# 표준 입력 예제
'''
a = int(input()) 정수형 변수 1개 입력 받는 예제
b, c = map(int, input().split()) 정수형 변수 2개 입력 받는 예제
d = float(input()) 실수형 변수 1개 입력 받는 예제
e, f, g = map(float, input().split()) 실수형 변수 3개 입력 받는 예제
h = input() 문자열 변수 1개 입력 받는 예제
'''
# 표준 출력 예제
'''
a, b = 6, 3
c, d, e = 1.0, 2.5, 3.4
f = "ABC"
print(a) 정수형 변수 1개 출력하는 예제
print(b, end = " ") 줄바꿈 하지 않고 정수형 변수와 공백을 출력하는 예제
print(c, d, e) 실수형 변수 3개 출력하는 예제
print(f) 문자열 1개 출력하는 예제
'''
####import sys
'''
아래의 구문은 input.txt 를 read only 형식으로 연 후,
앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
아래 구문을 이용하면 이후 입력을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 구문을 사용하셔도 좋습니다.
아래 구문을 사용하기 위해서는 import sys가 필요합니다.
단, 채점을 위해 코드를 제출하실 때에는 반드시 아래 구문을 지우거나 주석 처리 하셔야 합니다.
'''
#sys.stdin = open("./sample_input_1019", "r")
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
# ///////////////////////////////////////////////////////////////////////////////////
n, k_len = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
## 문제 수행
##max_len = max(max(row) for row in a)
answer = -1
def go(b):
global answer
max_len = max(max(row) for row in a)
for i in range(n):
for j in range(n):
if a[i][j] == max_len:
q = deque()
q.append((i, j, 1))
check = [[False] * n for _ in range(n)]
check[i][j] = True
ok = False
route = [(i, j)]
res = [[-1]*n for _ in range(n)]
res[i][j] = 1
while q:
x, y, depth = q.popleft()
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if 0 <= nx < n and 0 <= ny < n:
if (check[nx][ny] == False) or (res[nx][ny] < res[x][y]): ## (추가 주의 !!) 이미 방문했던 곳이지만 더 확인
if b[x][y] > b[nx][ny]:
q.append((nx, ny, depth + 1))
check[nx][ny] = True
route.append((nx, ny))
##res[nx][ny] = max(res[x][y] + 1, res[x][y]) ## (주의 !!)
res[nx][ny] = res[x][y] + 1
# 답 비교
if answer < depth:
answer = depth
# print(i, j, depth)
# print(route)
# for row in check:
# print(row)
# print()
# for row in res:
# print(row)
# print()
## (1) 그냥 탐색
go(a)
## (2) 경사로를 1에서부터 최대 K 만큼까지 깎아보기 - 딱 한칸만
for i in range(n):
for j in range(n):
for k_len_num in range(1, k_len + 1):
copy = [row[:] for row in a]
copy[i][j] -= k_len_num
go(copy)
print('#{0} {1}'.format(test_case, answer))
# ///////////////////////////////////////////////////////////////////////////////////
