#include <cstdio>
#include <queue>
// #define DEBUG 1

using namespace std;

struct edge
{
    int u, v;
    int s;
};

struct place {
    int depth;
    bool visited;
}

bool operator< (edge a, edge b)
{
    if (a.s < b.s)
        return true;
    else
        return false;
}

void print_map(int **map, int n) {
    #ifdef DEBUG
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    #endif
}

int find (int x, int* parent)
{
    /**********************
    * PLACE FOR YOUR CODE *
    **********************/
}

void unia (int x, int y, int* parent, int* rank)
{
    /**********************
    * PLACE FOR YOUR CODE *
    **********************/
}

void inArray(int a, int b, int n) {
    return a >= 0 && a < n && b >= 0 && b < n;
}

int draught_calculator(int **map, bool** visited, int x, int y, int n, int k, bool &reached) {
    if (x == 0 && y == 0) {
        for (int i = 0; i < n; i++) {
            visited[i] = new bool[n];
            for (int j = 0; j < n; j++) visited[i][j] = false;
        }
    }
    if (x == n - 1 && y == n - 1) {
        reached = true;
        return k;
    }
    visited[x][y] = true;
    for (int i = 1; i >= -1; i--) {
        for (int j = 1; j >= -1; j--) {
            if (abs(i) == abs(j)) continue;
            if (inArray(x + i, y + j, n) && !visited[x + i][y + j] && map[x + i][y + j] > k) {
                draught_calculator(map, visited, x + i, y + j, n, k);
            }
        }
    }
    if (x == 0 && y == 0) {
        for (int i = 0; i < n; i++) delete[] visited[i];
        delete[] visited;
        return reached ? k : draught_calculator(map, NULL, 0, 0, n, k - 1, reached);
    }
}

int main ()
{
    int Z;
    scanf("%d", &Z);
    while(Z--)
    {
        int n, k;
        scanf ("%d %d", &n, &k);
        int **map = new int*[n];
        for (int i = 0; i < n; i++)
            map[i] = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &map[i][j]);
            }
        }

        print_map(map, n);

        bool reached = false;
        int result = draught_calculator(map, NULL, 0, 0, n, k, reached);

        printf ("%d\n", result);

        for (int i = 0; i < n; i++)
            delete[] map[i];
        delete[] map;

    }
}