#include<bits/stdc++.h>
using namespace std;
int n,q,pr[410][410],a[410][410],pr2[410][410];
int u1[410][410],u2[410][410];
#define pb push_back
const int M=6e6+10,mod=1e9+7,W=131;
int qpow(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*a*c%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
mt19937 rnd(time(0));
#define pi pair<int,int>
#define fi first
#define se second
int ls[M],rs[M],s1[M],s2[M],cn;
int T1[410][410],T2[410][410],pw[160010],WI[160100];
bool cp1(int p,int q,int l=1,int r=n*n){
    if(l==r)return s1[p]>s1[q];
    int mi=(l+r)>>1;
    if(s2[rs[p]]==s2[rs[q]])return cp1(ls[p],ls[q],l,mi);
    return cp1(rs[p],rs[q],mi+1,r);
}
bool cp2(pi p,pi q,int l=1,int r=n*n){
    if(l==r)return s1[p.fi]+s1[p.se]>s1[q.fi]+s1[q.se];
    int mi=(l+r)>>1;
    int k1=s2[rs[p.fi]]+s2[rs[p.se]];if(k1>=mod)k1-=mod;
    int k2=s2[rs[q.fi]]+s2[rs[q.se]];if(k2>=mod)k2-=mod;
    if(k1==k2)return cp2({ls[p.fi],ls[p.se]},{ls[q.fi],ls[q.se]},l,mi);
    return cp2({rs[p.fi],rs[p.se]},{rs[q.fi],rs[q.se]},mi+1,r);
}
void up(int &p,int lst,int x,int l=1,int r=n*n){
    p=++cn;ls[p]=ls[lst],rs[p]=rs[lst],s1[p]=s1[lst]+1,s2[p]=s2[lst]+WI[x];
    if(s2[p]>=mod)s2[p]-=mod;
    if(l==r)return;
    int mi=(l+r)>>1;
    if(x<=mi)up(ls[p],ls[lst],x,l,mi);
    else up(rs[p],rs[lst],x,mi+1,r);
}
pi o[410][410];
int v1[410][410],v2[410][410],v3[410][410];
void sol(){
    cn=0;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
    pw[0]=1;
    for(int i=1;i<=n*n;i++)pw[i]=1ll*n*n*pw[i-1]%mod,WI[i]=rnd()%mod;
    for(int i=0;i<=n+1;i++)for(int j=0;j<=n+1;j++)
    T1[i][j]=T2[i][j]=u1[i][j]=u2[i][j]=v1[i][j]=v2[i][j]=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        pr[i][j]=cp1(T1[i-1][j],T1[i][j-1]);
        up(T1[i][j],pr[i][j]?T1[i-1][j]:T1[i][j-1],a[i][j]);
        v1[i][j]=((pr[i][j]?v1[i-1][j]:v1[i][j-1])+pw[a[i][j]])%mod;
    }
    for(int i=n;i;i--)for(int j=n;j;j--){
        pr2[i][j]=cp1(T2[i+1][j],T2[i][j+1]);
        up(T2[i][j],pr2[i][j]?T2[i+1][j]:T2[i][j+1],a[i][j]);
        v2[i][j]=((pr2[i][j]?v2[i+1][j]:v2[i][j+1])+pw[a[i][j]])%mod;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            o[i][j]={T1[i][j],pr2[i][j]?T2[i+1][j]:T2[i][j+1]};
            v3[i][j]=((v1[i][j]+v2[i][j]-pw[a[i][j]])%mod+mod)%mod;
            if(j==1)u1[i][j]=j;
            else{
                int z=u1[i][j-1];
                u1[i][j]=cp2(o[i][z],o[i][j])?z:j;
            }
            if(i==1)u2[i][j]=i;
            else{
                int z=u2[i-1][j];
                u2[i][j]=cp2(o[z][j],o[i][j])?z:i;
            }
        }
    }
    for(int i=1,a,b,c,d;i<=q;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        c--,b++,a--,d++;
        pi ot={0,0};int ans=0;
        if(b<=n&&c>=1){
            ot=o[b][u1[b][c]],
            ans=v3[b][u1[b][c]];
        }
        if(a>=1&&d<=n){
            if(!ot.fi||cp2(o[u2[a][d]][d],ot))
            ans=v3[u2[a][d]][d];
        }
        printf("%d\n",ans);
    }
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}