Rare_elements_Samsung

/*
5
5 2
4 3
3 4
1 1 0 0 0
1 1 0 0 0
1 1 1 1 1
1 1 1 0 1
1 1 1 1 1
8 2
5 6
6 4
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 0
1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
10 3
8 2
5 3
7 1
0 0 0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 0
1 0 0 1 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
15 4
11 15
15 9
1 2
14 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 0 1 1 1 1 1 1 1 0 1
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1
20 4
13 6
20 4
1 2
17 16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0

output:-
1
2
2
12
15
*/

#include <iostream>
using namespace std;

class que{
    int row[1000];
    int col[1000];
    int front,rear;
    public:
        que(){
            front=rear=0;
        }
        void push(int x,int y){
            row[rear]=x;
            col[rear]=y;
            rear++;
        }
        void pop(){
            front++;
        }
        void top(int *x,int *y){
            *x=row[front];
            *y=col[front];
        }
        bool empty(){
            if(front==rear) return true;
            return false;
        }
};

struct points{
    int x, y;
};

int mat[21][21];
int n,m;

bool canChek(int x,int y,bool visited[][25]){
    if(x>=0 && x<n && y>=0 && y<n && visited[x][y]==false && mat[x][y]==1)
        return true;
    return false;
}

int bfs(int s1, int s2,int d1,int d2){
    bool visited[25][25]={false};
    int distance[100][100];

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            distance[i][j]=-1;

    que q;
    q.push(s1,s2);
    visited[s1][s2]=true;
    distance[s1][s2]=0;

    int ans=0;
    while(!q.empty()){
        int x,y;
        q.top(&x,&y);
        q.pop();

        // if(x==d1 && y==d2) return distance[d1][d2];
        int dx[]={-1,0,1,0};
        int dy[]={0,1,0,-1};
        for(int i=0; i<4; i++){
            int m = x + dx[i];
            int n = y + dy[i];

            if(canChek(m,n,visited)){
                q.push(m,n);
                visited[m][n]=true;
                distance[m][n]= distance[x][y] +1;
            }
        }
        // cout<<"hello ";
    }
    return distance[d1][d2];
}

int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;

        //rare elements location
        points rare[5];
        for(int i=0; i<m; i++){
            cin>>rare[i].x>>rare[i].y;
            // rare[i].x--;
            // rare[i].y--;
        }

        //matrix representing roads
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin>>mat[i][j];

        int shortest_longest_distance=99999;

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(mat[i][j]==1){
                    int longest_distance=0;
                    for(int k=0; k<m; k++){
                        int ans= bfs(i,j,rare[k].x-1,rare[k].y-1);
                        longest_distance = max(longest_distance,ans);
                    }
                    shortest_longest_distance = min(longest_distance,shortest_longest_distance);
                }
            }
        }
        cout<<shortest_longest_distance<<endl;
    }
}