#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;

		using vvp = vector<vector<pii>>;
		vvp fs(n, vector<pii>(n, pii{-1, -1})), gs(fs);
		auto get = [&](const vvp &bs, pii now) {
			vi res;
			while (1) {
				auto [x, y] = now;
				if (x < 0 || x >= n || y < 0 || y >= n) break;
				res.push_back(as[x][y]);
				now = bs[x][y];
			}
			return res;
		};

		rep(i, 0, n - 1) {
			rep(j, 0, n - 1) {
				vi xs, ys;
				if (i > 0) xs = move(get(fs, pii{i - 1, j}));
				if (j > 0) ys = move(get(fs, pii{i, j - 1}));
				sort(all(xs), greater<int>());
				sort(all(ys), greater<int>());
				if (xs > ys) fs[i][j] = pii{i - 1, j};
				else fs[i][j] = pii{i, j - 1};
			}
		}
		revrep(i, 0, n - 1) {
			revrep(j, 0, n - 1) {
				vi xs, ys;
				if (i != n - 1) xs = move(get(gs, pii{i + 1, j}));
				if (j != n - 1) ys = move(get(gs, pii{i, j + 1}));
				sort(all(xs), greater<int>());
				sort(all(ys)), greater<int>();
				if (xs > ys) gs[i][j] = pii{i + 1, j};
				else gs[i][j] = pii{i, j + 1};
			}
		}

		vvp pre(n, vector<pii>(n)), suf(pre);
		auto get2 = [&](pii a) {
			vi xs;
			auto [i, j] = a;
			const auto &x1 = get(fs, a);
			const auto &x2 = get(gs, gs[i][j]);
			xs.insert(xs.end(), all(x1));
			xs.insert(xs.end(), all(x2));
			sort(all(xs), greater<int>());
			return xs;
		};
		rep(i, 0, n - 1) {
			pre[i][0] = {i, 0};
			rep(j, 1, n - 1) {
				vi xs = get2(pre[i][j - 1]);
				vi ys = get2(pii{i, j});
				if (xs > ys) pre[i][j] = pre[i][j - 1];
				else pre[i][j] = {i, j};
			}
			suf[i][n - 1] = {i, n - 1};
			revrep(j, 0, n - 2) {
				vi xs = get2(suf[i][j + 1]);
				vi ys = get2(pii{i, j});
				if (xs > ys) suf[i][j] = suf[i][j + 1];
				else suf[i][j] = {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, get2(pii{x1 - 1, y2 + 1}));
			}
			if (x2 != n - 1 && y1 != 0) {
				chmax(res, get2(pii{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;
}