import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.Stack;

import java.util.StringTokenizer;



class Solution {


static boolean Debug = false;

static int MapSize, DigSize;

static int Highset;

static int[][] Map;

static int[][] Visited;

private static int T;

private static int Answer;


public static void main(String args[]) throws Exception {


BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (4).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


int TestSize = Integer.parseInt(br.readLine());

for (T = 1; T <= TestSize; T++) {


// MapSize , DigSize , 본문 예제

st = new StringTokenizer(br.readLine());

MapSize = Integer.parseInt(st.nextToken());

DigSize = Integer.parseInt(st.nextToken());


// 지도데이터

Map = new int[MapSize][];

Visited = new int[MapSize][];

Highset = 0;

for (int i = 0; i < MapSize; i++) {

Map[i] = new int[MapSize];

Visited[i] = new int[MapSize];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < MapSize; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

if (Highset < Map[i][j]) {

Highset = Map[i][j];

}

}

}


// 길찾기 (시작점은 가장 큰 수)

ArrayList<Integer> startList = new ArrayList<>();

for (int i = 0; i < MapSize; i++) {

for (int j = 0; j < MapSize; j++) {

if (Highset == Map[i][j]) {

startList.add(i * MapSize + j);

}

}

}


Answer = 0;

for (int item : startList) {

findPath(item / MapSize, item % MapSize, 0);

}


System.out.println(String.format("#%d %d", T, Answer));

}


}


static int rotX[] = { 0, 1, 0, -1 };

static int rotY[] = { 1, 0, -1, 0 };

static Stack<Integer> pStack = new Stack<>();


// 모든 경로를 탐색하는 알고리즘

private static void findPath(int y, int x, int hint) {

Visited[y][x] = 1;

pStack.push(Map[y][x]);


Boolean isLast = true;


for (int i = 0; i < 4; i++) {

int moveY = y + rotY[i];

int moveX = x + rotX[i];


int path = isRight(moveY, moveX, Map[y][x]);

if (path == 1) { // 힌트 없이 전진

findPath(moveY, moveX, hint);

isLast = false;

} else if (path == 0 && hint == 0) {

// 힌트 사용하여 전진

findPath(moveY, moveX, 1);

isLast = false;

} else {

// 못간다.

}

}

if (isLast) {

// 모든 가능한 경로에 도달한 경우

int count = countLength(pStack);

if (count>0) {

if(Answer < count) {

Answer = count;

}

}

}


Visited[y][x] = 0;

pStack.pop();

}


// 탐색경로에서 길이를 체크해주는 함수

private static int countLength(Stack<Integer> inStack) {


ArrayList<Integer> list = new ArrayList<>();

list.addAll(inStack);


// [9, 7, 7, 3, 2]

// a = 7, b= 7, c =3

int temp = list.get(0);

int findIndex = -1;

int size = list.size();

for (int i = 1; i < size; i++) {

if (temp > list.get(i)) {

temp = list.get(i);

} else {

findIndex = i; // found b-index

break;

}

if(i==size-1) {

return list.size();

}

}


int a, b, c; // 오름차순

a = list.get(findIndex - 1);

b = list.get(findIndex);

c = (findIndex + 1 != list.size()) ? list.get(findIndex + 1) : -1;


if(((b - a) + 1 <= DigSize)) { // 땅을 팔 수 있는 경우

if(a > c + 1) { // c가 a보다 2이상 차이 나는 경우, 이 후 순서도 보장

return size;

}else { // c가 a보다 크거나 같은 경우

return findIndex + 1; // b까지 옳음  (b_index + 1개 )

}

}else {

return findIndex ; // b-1 까지 옳음 (b_index-1 + 1개 )

}

}


// 경로 가능성 판단

private static int isRight(int y, int x, int num) {

// 갈수 있으면 1, 숫자 크기 때문에 못가면 0, 범위 밖이면 -1, 방문했던 곳 -1

if (y < 0 || y >= MapSize || x < 0 || x >= MapSize) {

return -1;

}


if (Visited[y][x] == 1) {

return -1;

}

return Map[y][x] < num ? 1 : 0;

}



private static void log(String input) {

System.out.println(input);

}


}

+ Recent posts