#include <cstdio>
#include <queue>

using namespace std;

struct tile {
    int i, j;
    int d;
};

struct TileComparator {
    bool operator()(const tile* lhs, const tile* rhs) const {
        return lhs->d < rhs->d;
    }
};

int find(int x, int* parent) {
    while(parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

void unia(int x, int y, int* parent) {
    int rootX = find(x, parent);
    int rootY = find(y, parent);
    parent[rootX] = rootY;
}

const int DX[4]={1,0,-1,0};
const int DY[4]={0,1,0,-1};
int draught_calculator(tile*** map, priority_queue<tile*,  vector<tile*>, TileComparator> Q, int n, int k) {
    //if(n==1) return map[0][0]->d; doesn't work either way
    int* parent = new int[n*n];
    for(int i=0;i<n*n;i++) {
        parent[i] = i;
    }

    while(!Q.empty() && find(0, parent) != find(n*n-1, parent)) {
        tile* tmp = Q.top(); Q.pop();
        if(tmp->d < k) {
            k = tmp->d;
        }

        for (int i=0;i<4;i++) {
            int x = tmp->i + DX[i];
            int y = tmp->j + DY[i];
            if (x>=0 && x<n && y>=0 && y<n && map[x][y]->d >= tmp->d) {
                unia(n*tmp->i+tmp->j, n*x+y, parent);
            }
        }
    }
    return k;
}

int main ()
{
    int Z;
    scanf("%d", &Z);
    while(Z--)
    {
        int n, k;
        scanf ("%d %d", &n, &k);

        tile ***map = new tile**[n];
        for (int i = 0; i < n; i++)
            map[i] = new tile*[n];

        priority_queue<tile*, vector<tile*>, TileComparator> Q;
        int depth;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                tile *til = new tile;
                til->i = i;
                til->j = j;
                scanf("%d", &til->d);
                Q.push(til);
                map[i][j] = til;
            }
        }

        int result = draught_calculator(map, Q, n, k);
        printf ("%d\n", k-result);
        for (int i = 0; i < n; i++)
            delete[] map[i];
        delete[] map;
    }
}