# 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],pre[410][410],suf[410][410],val[20000010];
template<typename T>
inline void upd(int &x,const T &y){x=(x+y)%p1;}
inline Hash Lc(const Hash &rt){return {lc[rt.first],lc[rt.second]};}
inline Hash Rc(const Hash &rt){return {rc[rt.first],rc[rt.second]};}
inline int Cnt(const Hash &rt){return cnt[rt.first]+cnt[rt.second];}
inline int Sum(const Hash &rt){return (sum[rt.first]+sum[rt.second])%p1;}
inline Hash Val(const Hash &rt){return val[rt.first]+val[rt.second];}
void pushup(int rt)
{
	sum[rt]=(sum[lc[rt]]+sum[rc[rt]])%p1;
	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];cnt[cur]=cnt[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);
}
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[rc[r1]]!=val[rc[r2]]) return cmp(rc[r1],rc[r2],mid+1,r);
	else return cmp(lc[r1],lc[r2],l,mid);
}
bool cmp(const Hash &r1,const Hash &r2,int l,int r)
{
	if(!r1.first && !r1.second) return false;
	else if(!r2.first && !r2.second) return true;
	if(l==r) return Cnt(r1)>Cnt(r2);
	int mid=(l+r)/2;
	if(Val(Rc(r1))!=Val(Rc(r2))) return cmp(Rc(r1),Rc(r2),mid+1,r);
	else return cmp(Lc(r1),Lc(r2),l,mid);
}
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]);
				pre[i][j]=suf[i][j]={f[i][j],g[i][j]};
				update(g[i][j],1,N,a[i][j]);
			}
		for(int i=1;i<=n;i++)
		{
			for(int j=2;j<=n;j++) pre[i][j]=(cmp(pre[i][j],pre[i][j-1],1,N)?pre[i][j]:pre[i][j-1]);
			for(int j=n-1;j;j--) suf[i][j]=(cmp(suf[i][j],suf[i][j+1],1,N)?suf[i][j]:suf[i][j+1]);
		}
		while(q--)
		{
			Hash ans={0,0};
			scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
			if(x2<n && y1>1) ans=(cmp(ans,pre[x2+1][y1-1],1,N)?ans:pre[x2+1][y1-1]);
			if(x1>1 && y2<n) ans=(cmp(ans,suf[x1-1][y2+1],1,N)?ans:suf[x1-1][y2+1]);
			printf("%d\n",Sum(ans));
		}
		memset(lc+1,0,sizeof(int)*tot);
		memset(rc+1,0,sizeof(int)*tot);
		memset(cnt+1,0,sizeof(int)*tot);
		memset(sum+1,0,sizeof(int)*tot);
		memset(val+1,0,sizeof(Hash)*tot);
		tot=0;
	}
	return 0;
}