# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Hash=pair<int,int>;
constexpr int p1=1e9+7,p2=1e9+9,Base=998244353;
inline Hash operator+(const Hash &x,const Hash &y){return {(x.first+y.first)%p1,(x.second+y.second)%p2};}
inline Hash &operator+=(Hash &x,const Hash &y){return x=x+y;}
inline Hash operator-(const Hash &x,const Hash &y){return {(x.first+p1-y.first)%p1,(x.second+p2-y.second)%p2};}
inline Hash operator*(const Hash &x,const Hash &y){return {(ll)x.first*y.first%p1,(ll)x.second*y.second%p2};}
int N,a[410][410],f[410][410],g[410][410],pwn[160010],lc[20000010],rc[20000010],cnt[20000010],sum[20000010],tot=0;
Hash pw[160010],val[20000010];
template<typename T>
inline void upd(int &x,const T &y){x=(x+y)%p1;}
void pushup(int rt)
{
	sum[rt]=sum[lc[rt]]+sum[rc[rt]];
	val[rt]=val[lc[rt]]+val[rc[rt]];
}
void update(int &rt,int l,int r,int x)
{
	int cur=++tot;
	lc[cur]=lc[rt];rc[cur]=rc[rt];sum[cur]=sum[rt];val[cur]=val[rt];rt=cur;
	if(l==r) return cnt[rt]++,upd(sum[rt],pwn[l]),val[rt]+=pw[l],void();
	int mid=(l+r)/2;
	if(x<=mid) update(lc[rt],l,mid,x);
	else update(rc[rt],mid+1,r,x);
	pushup(rt);
}
int merge(int r1,int r2,int l,int r)
{
	if(!r1 || !r2) return r1+r2;
	int rt=++tot;
	if(l==r)
	{
		cnt[rt]=cnt[lc[rt]]+cnt[rc[rt]];
		sum[rt]=(sum[lc[rt]]+sum[rc[rt]])%p1;
		val[rt]=val[lc[rt]]+val[rc[rt]];
		return rt;
	}
	int mid=(l+r)/2;
	lc[rt]=merge(lc[r1],lc[r2],l,mid);
	rc[rt]=merge(rc[r1],rc[r2],mid+1,r);
	pushup(rt);
	return rt;
}
bool cmp(int r1,int r2,int l,int r)
{
	if(!r1) return false;
	else if(!r2) return true;
	if(l==r) return cnt[r1]>cnt[r2];
	int mid=(l+r)/2;
	if(val[lc[r1]]!=val[lc[r2]]) return cmp(lc[r1],lc[r2],l,mid);
	else return cmp(rc[r1],rc[r2],mid+1,r);
}
int main()
{
	int T,n,q,x1,x2,y1,y2;
	cin>>T;
	while(T--)
	{
		scanf("%d%d",&n,&q);N=n*n;
		pwn[0]=1;
		for(int i=1;i<=N;i++) pwn[i]=(ll)pwn[i-1]*N%p1;
		pw[0]={1,1};
		for(int i=1;i<=N;i++) pw[i]=pw[i-1]*Hash{Base,Base};
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&a[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				if(i==1 && j==1) f[i][j]=0;
				else if(i==1) f[i][j]=f[i][j-1];
				else if(j==1) f[i][j]=f[i-1][j];
				else f[i][j]=(cmp(f[i][j-1],f[i-1][j],1,N)?f[i][j-1]:f[i-1][j]);
				update(f[i][j],1,N,a[i][j]);
			}
		for(int i=n;i;i--)
			for(int j=n;j;j--)
			{
				if(i==n && j==n) g[i][j]=0;
				else if(i==n) g[i][j]=g[i][j+1];
				else if(j==n) g[i][j]=g[i+1][j];
				else g[i][j]=(cmp(g[i][j+1],g[i+1][j],1,N)?g[i][j+1]:g[i+1][j]);
				f[i][j]=merge(f[i][j],g[i][j],1,N);
				update(g[i][j],1,N,a[i][j]);
			}
		for(int i=1;i<=n;i++) memcpy(g[i]+1,f[i]+1,sizeof(int)*n);
		for(int i=1;i<=n;i++)
		{
			for(int j=2;j<=n;j++) f[i][j]=(cmp(f[i][j],f[i][j-1],1,N)?f[i][j]:f[i][j-1]);
			for(int j=n-1;j;j--) g[i][j]=(cmp(g[i][j],g[i][j+1],1,N)?g[i][j]:g[i][j+1]);
		}
		while(q--)
		{
			int ans=0;
			scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
			if(x2<n && y1>1) ans=(cmp(ans,f[x2+1][y1-1],1,N)?ans:f[x2+1][y1-1]);
			if(x1>1 && y2<n) ans=(cmp(ans,g[x1-1][y2+1],1,N)?ans:g[x1-1][y2+1]);
			printf("%d\n",sum[ans]);
		}
	}
	return 0;
}