#include "bits/stdc++.h"

using namespace std;

template <typename T>
class flow_graph {
public:
    static constexpr T eps = (T) 1e-9;

    struct edge {
        int to;
        T c;
        T f;
        int rev;
    };

    vector<vector<edge>> g;
    vector<int> ptr;
    vector<int> d;
    vector<int> q;
    vector<int> cnt_on_layer;
    vector<int> prev_edge;
    bool can_reach_sink;

    int n;
    int st, fin;
    T flow;

    flow_graph(int _n, int _st, int _fin) : n(_n), st(_st), fin(_fin) {
        assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin);
        g.resize(n);
        ptr.resize(n);
        d.resize(n);
        q.resize(n);
        cnt_on_layer.resize(n + 1);
        prev_edge.resize(n);
        flow = 0;
    }

    void add(int from, int to, T forward_cap, T backward_cap) {
        assert(0 <= from && from < n && 0 <= to && to < n);
        int from_size = g[from].size();
        int to_size = g[to].size();
        g[from].push_back({to, forward_cap, 0, to_size});
        g[to].push_back({from, backward_cap, 0, from_size});
    }

    bool expath() {
        fill(d.begin(), d.end(), n);
        q[0] = fin;
        d[fin] = 0;
        fill(cnt_on_layer.begin(), cnt_on_layer.end(), 0);
        cnt_on_layer[n] = n - 1;
        cnt_on_layer[0] = 1;
        int beg = 0, end = 1;
        while (beg < end) {
            int i = q[beg++];
            for (const edge &e : g[i]) {
                const edge &back = g[e.to][e.rev];
                if (back.c - back.f > eps && d[e.to] == n) {
                    cnt_on_layer[d[e.to]]--;
                    d[e.to] = d[i] + 1;
                    cnt_on_layer[d[e.to]]++;
                    q[end++] = e.to;
                }
            }
        }
        return (d[st] != n);
    }

    T augment(int &v) {
        T cur = numeric_limits<T>::max();
        int i = fin;
        while (i != st) {
            const edge &e = g[i][prev_edge[i]];
            const edge &back = g[e.to][e.rev];
            cur = min(cur, back.c - back.f);
            i = e.to;
        }
        i = fin;
        while (i != st) {
            edge &e = g[i][prev_edge[i]];
            edge &back = g[e.to][e.rev];
            back.f += cur;
            e.f -= cur;
            i = e.to;
            if (back.c - back.f <= eps) {
                v = i;
            }
        }
        return cur;
    }

    int retreat(int v) {
        int new_dist = n - 1;
        for (const edge &e : g[v]) {
            if (e.c - e.f > eps && d[e.to] < new_dist) {
                new_dist = d[e.to];
            }
        }
        cnt_on_layer[d[v]]--;
        if (cnt_on_layer[d[v]] == 0) {
            if (new_dist + 1 > d[v]) {
                can_reach_sink = false;
            }
        }
        d[v] = new_dist + 1;
        cnt_on_layer[d[v]]++;
        if (v != st) {
            v = g[v][prev_edge[v]].to;
        }
        return v;
    }

    T max_flow() {
        can_reach_sink = true;
        for (int i = 0; i < n; i++) {
            ptr[i] = (int) g[i].size() - 1;
        }
        if (expath()) {
            int v = st;
            while (d[st] < n) {
                while (ptr[v] >= 0) {
                    const edge &e = g[v][ptr[v]];
                    if (e.c - e.f > eps && d[e.to] == d[v] - 1) {
                        prev_edge[e.to] = e.rev;
                        v = e.to;
                        if (v == fin) {
                            flow += augment(v);
                        }
                        break;
                    }
                    ptr[v]--;
                }
                if (ptr[v] < 0) {
                    ptr[v] = (int) g[v].size() - 1;
                    v = retreat(v);
                    if (!can_reach_sink) {
                        break;
                    }
                }
            }
        }
        return flow;
    }
};

using ll = long long;

const int N = int(1e5) + 22;
const ll inf = (ll) 1e18;
int n, m, a[3][N], b[3][N];
ll A[N], B[N];
ll pa[3][N], pb[3][N];
pair<int, int> seg[3][64];
ll dp[N][64];

bool check(int ans) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            pa[i][j + 1] = pa[i][j] + a[i][j];
            pb[i][j + 1] = pb[i][j] + b[i][j];
        }
    }
    int pw = 1 << n;
    for (int msk = 0; msk < pw * pw; msk++) {
        for (int i = 0; i < n; i++) {
            seg[i][msk] = {int(1e9), -int(1e9)};
            for (int s = 0; s < 2; s++) {
                for (int j = 0; j < n; j++) {
                    if (msk >> (s * n + j) & 1) {
                        int l = s - 1 - ans, r = s - 1 + ans;
                        l += abs(i - j);
                        r -= abs(i - j);
                        if (l <= r) {
                            seg[i][msk].first = min(seg[i][msk].first, l);
                            seg[i][msk].second = max(seg[i][msk].second, r);
                        }
                    }
                }
            }
            if (seg[i][msk].first > seg[i][msk].second) {
                seg[i][msk] = {-int(1e9), -int(1e9)};
            }
        }
    }
    fill(dp[0], dp[0] + pw * pw, -inf);
    dp[0][0] = 0;
    vector<int> deltas = {-1, -ans * 2 + 2, -ans * 2 + 1, -ans * 2};
    for (int i = 1; i <= m; i++) {
        fill(dp[i], dp[i] + pw * pw, -inf);
        int pi = i - 1;
        for (int msk = 0; msk < pw * pw; msk++) {
            if (dp[pi][msk] <= -inf) {
                continue;
            }
            if (pi != i - 1 && (msk / pw)) {
                continue;
            }
            if (pi < i - 2 && msk) {
                continue;
            }
            for (int add = 0; add < pw; add++) {
                ll val = dp[pi][msk];
                if (add & 1) val += b[0][i - 1];
                if (add & 2) val += b[1][i - 1];
                if (add & 4) val += b[2][i - 1];
                int nmsk = msk / pw + add * pw;
                for (int j = 0; j < n; j++) {
                    if (seg[j][nmsk].first == -int(1e9)) {
                        continue;
                    }
                    int l = min(m - 1, max(0, seg[j][nmsk].first + i - 1));
                    int r = min(m - 1, max(0, seg[j][nmsk].second + i - 1));
                    if (seg[j][msk].first == -int(1e9)) {
                        val -= pa[j][r + 1] - pa[j][l];
                        continue;
                    }
                    int l2 = min(m - 1, max(0, seg[j][msk].first + pi - 1));
                    int r2 = min(m - 1, max(0, seg[j][msk].second + pi - 1));
                    if (l <= l2 && r2 <= r) {
                        val -= pa[j][r + 1] - pa[j][l];
                        val += pa[j][r2 + 1] - pa[j][l2];
                    } else if (l > r2) {
                        val -= pa[j][r + 1] - pa[j][l];
                    } else if (r > r2) {
                        val -= pa[j][r + 1] - pa[j][r2 + 1];
                    }
                }
                if (val > 0) {
                    return false;
                }
                dp[i][nmsk] = max(dp[i][nmsk], val);
            }
        }
    }
    return true;
}

void solve () {
    cin >> n >> m;
    fill(A, A + m, 0);
    fill(B, B + m, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            A[j] += a[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> b[i][j];
            B[j] += b[i][j];
        }
    }
    int lower_bound = 0;
    for (int i = 0, j = 0; i < m; i++) {
        while (A[i]) {
            while (!B[j]) {
                j++;
            }
            lower_bound = max(lower_bound, abs(i - j));
            ll mn = min(A[i], B[j]);
            A[i] -= mn;
            B[j] -= mn;
        }
    }
    for (int ans = lower_bound; ans <= lower_bound + 1; ans++) {
        if (check(ans)) {
            cout << ans << '\n';
            return;
        }
    }
    cout << lower_bound + 2 << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}
