#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a);i <= (b);++i)
#define per(i, a, b) for(int i = (a);i >= (b);--i)
#define lc (tr[k].ls)
#define rc (tr[k].rs)
#define lowbit(x) ((x) & -(x))
#define odd(x) ((x) & 1)
#define even(x) (!odd(x))
#define fir first
#define sec second
#define pb push_back
#define il inline
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define i128 __int128
#define f128 __float128
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << (x) << "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> using vc = vector<T>;
template<class Tx, class Ty>
il void chkmx(Tx& x, const Ty y) {x = max<common_type_t<Tx, Ty>>(x, y);}
template<class Tx, class Ty>
il void chkmn(Tx& x, const Ty y) {x = min<common_type_t<Tx, Ty>>(x, y);}
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
bool ms;

char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
template<class T>
il void read(T& x) {
    char ch;int f = 1;x = 0;
    do {ch = getchar();if(ch == '-')f = -1;} while(!isdigit(ch));
    do {x = x * 10 + (ch ^ 48);ch = getchar();} while(isdigit(ch));
    x *= f;
}

template<class T, class... Arg>
il void read(T& x, Arg&... nums) {
    read(x), read(nums...);
}

constexpr int p = 1e9 + 7;
struct mint {
    int x;
    mint(ll x = 0) : x(normalize(x % p)) {}
    static int normalize(int x) {
        if(x >= p)
            x -= p;
        else if(x < 0)
            x += p;
        return x;
    }
    int pw() const {return x;}
    mint pow(int b) const {
        ll ans = 1, a = x;
        while(b) {
            if(b & 1)
                ans = ans * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return ans;
    }
    mint inv() const {
        return pow(p - 2);
    }
    mint operator - () const {
        return (mint)normalize(p - x);
    }
    friend mint& operator += (mint& lhs, const mint& rhs) {
        lhs.x = normalize(lhs.x + rhs.x);
        return lhs;
    }
    friend mint& operator -= (mint& lhs, const mint& rhs) {
        lhs.x = normalize(lhs.x - rhs.x);
        return lhs;
    }
    friend mint& operator *= (mint& lhs, const mint& rhs) {
        lhs.x = 1ll * lhs.x * rhs.x % p;
        return lhs;
    }
    friend mint& operator /= (mint& lhs, const mint& rhs) {
        assert(rhs.pw());
        lhs.x = 1ll * lhs.x * rhs.inv().x % p;
        return lhs;
    }
    friend mint operator + (mint lhs, const mint& rhs) {
        lhs += rhs;
        return lhs;
    }
    friend mint operator - (mint lhs, const mint& rhs) {
        lhs -= rhs;
        return lhs;
    }
    friend mint operator * (mint lhs, const mint& rhs) {
        lhs *= rhs;
        return lhs;
    }
    friend mint operator / (mint lhs, const mint& rhs) {
        lhs /= rhs;
        return lhs;
    }
    friend istream& operator >> (istream& is, mint& a) {
        return is >> a.x;
    }
    friend ostream& operator << (ostream& os, const mint& a) {
        return os << a.x;
    }
    friend bool operator == (const mint& lhs, const mint& rhs) {
        return lhs.x == rhs.x;
    }
    friend bool operator != (const mint& lhs, const mint& rhs) {
        return lhs.x != rhs.x;
    }
};

il pair<ull, ull> operator + (const pair<ull, ull>& x, const pair<ull, ull>& y) {
    return {x.fir + y.fir, x.sec + y.sec};
}

const int N = 405, MAXN = N * N, LOG = 40;
int a[N][N];
int f[N][N], g[N][N], ct;
mint pw[MAXN];
pii mxr[N][N], mxc[N][N];
pair<ull, ull> w[MAXN];

struct Node {
    int ls, rs;
    int c;
    mint s;
    pair<ull, ull> w;
} tr[MAXN * LOG];

il int newNode() {
    tr[++ct] = Node();
    return ct;
}

il void push_up(int k) {
    tr[k].s = tr[lc].s + tr[rc].s;
    tr[k].w = tr[lc].w + tr[rc].w;
}

il void update(int& k, int k2, int p, int x, int L = 1, int R = MAXN) {
    k = newNode();
    if(L == R) {
        tr[k].c = tr[k2].c + x;
        tr[k].s = tr[k2].s + pw[p] * x;
        tr[k].w = tr[k2].w + pair<ull, ull>{w[L].fir * x, w[L].sec * x};
        return;
    }
    int mid = L + R >> 1;
    if(p <= mid) {
        rc = tr[k2].rs;
        update(lc, tr[k2].ls, p, x, L, mid);
    } else {
        lc = tr[k2].ls;
        update(rc, tr[k2].rs, p, x, mid + 1, R);
    }
    push_up(k);
}

il bool cmp(int k1, int k2) {
    if(tr[k1].w == tr[k2].w)
        return 0;
    int L = 1, R = MAXN;
    while(L != R) {
        int mid = L + R >> 1;
        if(tr[tr[k1].ls].w != tr[tr[k2].ls].w)
            R = mid, k1 = tr[k1].ls, k2 = tr[k2].ls;
        else
            L = mid + 1, k1 = tr[k1].rs, k2 = tr[k2].rs;
    }
    return tr[k1].c < tr[k2].c;
}

il bool cmp2(int k1, int k2, int k3, int k4) {
    if(tr[k1].w + tr[k2].w == tr[k3].w + tr[k4].w)
        return 0;
    int L = 1, R = MAXN;
    while(L != R) {
        int mid = L + R >> 1;
        if(tr[tr[k1].ls].w + tr[tr[k2].ls].w != tr[tr[k3].ls].w + tr[tr[k4].ls].w)
            R = mid, k1 = tr[k1].ls, k2 = tr[k2].ls, k3 = tr[k3].ls, k4 = tr[k4].ls;
        else
            L = mid + 1, k1 = tr[k1].rs, k2 = tr[k2].rs, k3 = tr[k3].rs, k4 = tr[k4].rs;
    }
    return tr[k1].c + tr[k2].c < tr[k3].c + tr[k4].c;
}

void solve() {
    int n, q;
    read(n, q);
    rep(i, 1, n) {
        rep(j, 1, n)
            read(a[i][j]);
    }
    pw[0] = 1;
    rep(i, 1, n * n)
        pw[i] = pw[i - 1] * n * n;
    ct = 0;
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    update(f[1][1], 0, a[1][1], 1);
    rep(i, 2, n) {
        update(f[1][i], f[1][i - 1], a[1][i], 1);
        update(f[i][1], f[i - 1][1], a[i][1], 1);
    }
    rep(i, 2, n) {
        rep(j, 2, n)
            update(f[i][j], max(f[i - 1][j], f[i][j - 1], cmp), a[i][j], 1);
    }
    update(g[n][n], 0, a[n][n], 1);
    per(i, n - 1, 1) {
        update(g[n][i], g[n][i + 1], a[n][i], 1);
        update(g[i][n], g[i + 1][n], a[i][n], 1);
    }
    per(i, n - 1, 1) {
        per(j, n - 1, 1)
            update(g[i][j], max(g[i + 1][j], g[i][j + 1], cmp), a[i][j], 1);
    }
    rep(i, 1, n) {
        rep(j, 1, n)
            update(g[i][j], g[i][j], a[i][j], -1);
    }
    rep(i, 1, n) {
        rep(j, 1, n) {
            mxr[i][j] = cmp2(f[i][j], g[i][j], mxr[i][j - 1].fir, mxr[i][j - 1].sec) ? mxr[i][j - 1] : pii{f[i][j], g[i][j]};
            mxc[i][j] = cmp2(f[i][j], g[i][j], mxc[i - 1][j].fir, mxc[i - 1][j].sec) ? mxc[i - 1][j] : pii{f[i][j], g[i][j]};
        }
    }
    while(q--) {
        int xl, xr, yl, yr;
        read(xl, xr, yl, yr);
        if((xl == 1 && yl == 1) || (xr == n && yr == n) || (xl == 1 && xr == n) || (yl == 1 && yr == n)) {
            cout << "0\n";
            continue;
        }
        pii mx = cmp2(mxr[xr + 1][yl - 1].fir, mxr[xr + 1][yl - 1].sec, mxc[xl - 1][yr + 1].fir, mxc[xl - 1][yr + 1].sec) ? mxc[xl - 1][yr + 1] : mxr[xr + 1][yl - 1];
        cout << tr[mx.fir].s + tr[mx.sec].s << "\n";
    }
}

bool mt;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cerr << fabs(&ms - &mt) / 1024 / 1024 << "\n";
    rep(i, 1, 160000)
        w[i] = {rnd(), rnd()};
    int t;
    read(t);
    while(t--)
        solve();
    cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}