#include<fstream>
#include<algorithm>
#define val first
#define ind second
using namespace std;
ifstream fi("matrice2.in");
ofstream fo("matrice2.out");
typedef struct qry{int rez,s,d,ind;} QRY;
QRY Q[20005],Aux1[20005],Aux2[20005];
int n,x,y,nq,q,i,j,k,M[305][305],P[300*300+5],Sz[300*300+5],Rez[20005],na1,na2;
pair<int,int> A[300*300+5];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

int p(int x)
{
    int cx=x;
    while(P[x]!=0)
        x=P[x];
    int aux;
    while(P[cx]!=0)
    {
        aux=P[cx];
        P[cx]=x;
        cx=aux;
    }
    return x;
}

void u(int x, int y)
{
    if(x==y)
        return;
    if(Sz[x]>Sz[y])
    {
        Sz[x]+=Sz[y];
        P[y]=x;
    }
    else
    {
        Sz[y]+=Sz[x];
        P[x]=y;
    }
}

bool check(int ind1, int ind2)
{
    return (p(ind1)==p(ind2));
}

void add(int ind)
{
    int x=(ind/n)+1;
    int y=ind%n;
    if(y==0)
    {
        x--;
        y=n;
    }
    int d;
    for(d=0; d<=3; d++)
        if(x+dx[d]>0 && x+dx[d]<=n && y+dy[d]>0 && y+dy[d]<=n && M[x][y]<=M[x+dx[d]][y+dy[d]])
            u(p(ind),p((x+dx[d]-1)*n+(y+dy[d])));
}

int main()
{
    fi>>n>>q;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
        {
            fi>>x;
            A[n*(i-1)+j]={x,n*(i-1)+j};
            M[i][j]=x;
        }
    sort(A+1,A+n*n+1);
    for(i=1; i<=q; i++)
    {
        Q[i].rez=0;
        Q[i].ind=i;
        fi>>x>>y;
        Q[i].s=n*(x-1)+y;
        fi>>x>>y;
        Q[i].d=n*(x-1)+y;
    }
    for(i=19; i>=0; i--)
    {
        for(j=1; j<=n*n; j++)
        {
            P[j]=0;
            Sz[j]=1;
        }
        na1=0;
        na2=0;
        for(j=q, k=n*n; j>=1; j--)
        {
            while(k>0 && A[k].val>=Q[j].rez+(1<<i))
                add(A[k--].ind);
            if(Q[j].rez+(1<<i)<=1000000 && check(Q[j].s,Q[j].d))
            {
                Q[j].rez+=(1<<i);
                Aux1[++na1]=Q[j];
            }
            else
                Aux2[++na2]=Q[j];
        }
        j=na1;
        k=na2;
        nq=0;
        while(j>0 && k>0)
        {
            if(Aux1[j].rez<=Aux2[k].rez)
                Q[++nq]=Aux1[j--];
            else
                Q[++nq]=Aux2[k--];
        }
        for(; j>0; j--)
            Q[++nq]=Aux1[j];
        for(; k>0; k--)
            Q[++nq]=Aux2[k];
    }
    for(i=1; i<=q; i++)
        Rez[Q[i].ind]=Q[i].rez;
    for(i=1; i<=q; i++)
        fo<<Rez[i]<<"\n";
    fi.close();
    fo.close();
    return 0;
}