#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1'000'000'007;

vector<ll> merge(const vector<ll> &A,const vector<ll> &B){
	int n=A.size();
	int m=B.size();
	vector<ll> C;
	int x=0,y=0;
	for (;x<n && y<m;){
		if (A[x]>=B[y]){
			C.push_back(A[x]);
			x++;	
		}
		else{
			C.push_back(B[y]);
			y++;	
		}
	}
	for (;x<n;x++) C.push_back(A[x]);
	for (;y<m;y++) C.push_back(B[y]);
	return C;
}

ll n,Q;
ll pw[400*400+50];
ll a[405][405];
vector<ll> pre[405][405],suf[405][405],f[405][405],g[405][405];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int Tcase=1;
	cin >> Tcase;
	for (;Tcase--;){
		cin >> n >> Q;
		
		pw[0]=1;
		for (int i=1;i<=n*n;i++) pw[i]=pw[i-1]*n%mod*n%mod;
		
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++) cin >> a[i][j];
			
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				if (i==1 && j==1){
					pre[i][j]={a[i][j]};
				}
				else if (i==1){
					pre[i][j]=merge(pre[i][j-1],{a[i][j]});
				}
				else if (j==1){
					pre[i][j]=merge(pre[i-1][j],{a[i][j]});
				}
				else{
					pre[i][j]=merge(max(pre[i-1][j],pre[i][j-1]),{a[i][j]});	
				}
			}
		}
		
		for (int i=n;i>=1;i--){
			for (int j=n;j>=1;j--){
				if (i==n && j==n){
					suf[i][j]={a[i][j]};
				}
				else if (i==n){
					suf[i][j]=merge(suf[i][j+1],{a[i][j]});
				}
				else if (j==n){
					suf[i][j]=merge(suf[i+1][j],{a[i][j]});
				}
				else{
					suf[i][j]=merge(max(suf[i+1][j],suf[i][j+1]),{a[i][j]});	
				}
			}
		}
			
		for (int i=2;i<=n;i++){
			for (int j=n-1;j>=1;j--){
				f[i][j]=merge(pre[i-1][j+1],suf[i][j+1]);
				if (i!=2){
					f[i][j]=max(f[i][j],f[i-1][j]);	
				}
				if (j!=n-1){
					f[i][j]=max(f[i][j],f[i][j+1]);	
				}
			}
		}
		
		for (int i=n-1;i>=1;i--){
			for (int j=2;j<=n;j++){
				g[i][j]=merge(pre[i+1][j-1],suf[i+1][j]);
				if (j!=2){
					g[i][j]=max(g[i][j],g[i][j-1]);	
				}
				if (i!=n-1){
					g[i][j]=max(g[i][j],g[i+1][j]);	
				}
			}
		}
		
		for (;Q--;){
			int r1,r2,c1,c2;
			cin >> r1 >> r2 >> c1 >> c2;
			vector<ll> route;
			bool flagf=(r1>=2 && c2<=n-1);
			bool flagg=(r2<=n-1 && c1>=2);
			
			if (flagf && flagg) route=max(f[r1][c2],g[r2][c1]);
			else if (flagf) route=f[r1][c2];
			else route=g[r2][c1];
			
			ll ans=0;
			for (auto x:route){
				ans=(ans+pw[x])%mod;
			}
			cout << ans << "\n";
		}
	}
	return 0;
}