#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); i++)
#define revrep(i, a, n) for (auto i = n; i >= (a); i--)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } else return 0; }
using namespace std;

template<class A, class B> string to_string(pair<A, B> p);
template<class A> string to_string(A v) {
	bool first = 1;
	string res = "{";
	for (auto x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(H h, T... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;


int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int cas; cin >> cas; while (cas--) {
		int n, q; cin >> n >> q;
		vvi as(n, vi(n));
		for (auto &vec: as) for (auto &x: vec) cin >> x;

		const int maxn = 400;
		static vi fs[maxn][maxn];
		static vi gs[maxn][maxn];
		rep(i, 0, n - 1) rep(j, 0, n - 1) {
			fs[i][j].clear();
			gs[i][j].clear();
		}
		rep(i, 0, n - 1) {
			rep(j, 0, n - 1) {
				auto &f = fs[i][j];
				if (i > 0) {
					if (sz(f) == 0) f = fs[i - 1][j];
					else chmax(f, fs[i - 1][j]);
				}
				if (j > 0) {
					if (sz(f) == 0) f = fs[i][j - 1];
					else chmax(f, fs[i][j - 1]);
				}
				int a = as[i][j];
				for (auto it = f.begin(); ; it++) {
					if (it == f.end() || a > *it) {
						f.insert(it, a);
						break;
					}
				}
			}
		}
		revrep(i, 0, n - 1) {
			revrep(j, 0, n - 1) {
				auto &g = gs[i][j];
				if (i != n - 1) {
					if (sz(g) == 0) g = gs[i + 1][j];
					else chmax(g, gs[i + 1][j]);
				}
				if (j != n - 1) {
					if (sz(g) == 0) g = gs[i][j + 1];
					else chmax(g, gs[i][j + 1]);
				}
				int a = as[i][j];
				for (auto it = g.begin(); ; it++) {
					if (it == g.end() || a > *it) {
						g.insert(it, a);
						break;
					}
				}
			}
		}
		rep(i, 0, n - 1) rep(j, 0, n - 1) {
			auto &g = gs[i][j];
			int a = as[i][j];
			for (auto it = g.begin(); ; it++) {
				if (*it == a) {
					g.erase(it);
					break;
				}
			}
		}
		
		static vi dp[maxn][maxn];
		rep(i, 0, n - 1) {
			rep(j, 0, n - 1) {
				merge(all(fs[i][j]), all(gs[i][j]), back_inserter(dp[i][j]), greater<int>());
			}
		}

		rep(i, 0, n - 1) {
			fs[i][0] = dp[i][0];
			rep(j, 1, n - 1) fs[i][j] = max(fs[i][j - 1], dp[i][j]);
			gs[i][n - 1] = dp[i][n - 1];
			revrep(j, 0, n - 2) gs[i][j] = max(gs[i][j + 1], dp[i][j]);
		}

		vi vs(n * n + 1);
		vs[0] = 1;
		const int mod = 1e9 + 7;
		rep(i, 1, n * n) vs[i] = 1ll * vs[i - 1] * (n * n) % mod;

		while (q--) {
			int x1, x2, y1, y2; cin >> x1 >> x2 >> y1 >> y2;
			x1--, y1--;
			x2--, y2--;
			static vi res; res.clear();
			if (y2 != n - 1 && x1 != 0) {
				chmax(res, gs[x1 - 1][y2 + 1]);
			}
			if (x2 != n - 1 && y1 != 0) {
				chmax(res, fs[x2 + 1][y1 - 1]);
			}
			assert(sz(res) > 0);
			int ans = 0;
			for (auto x: res) ans = (ans + vs[x]) % mod;
			printf("%d\n", ans);
		}
	}
	return 0;
}