#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, long long>;
using pli = pair<long long, int>;
using pll = pair<long long, long long>;
template <typename T>
using uset = unordered_set<T>;
template <typename T1, typename T2>
using umap = unordered_map<T1, T2>;

template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#ifndef _DEBUG
#pragma GCC optimize("O3,unroll-loops,fast-math")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

const int inf = 1e9;
const ll linf = 3e18;

template<int V>
struct MAX_FLOW {
    struct edge {
        ll u, c, f;
    };

    int N;
    vector<int> g[V];
    vector<edge> edges;

    void add_edge(int v, int u, ll c) {
        g[v].push_back(edges.size());
        edges.push_back({u, c, 0});
        g[u].push_back(edges.size());
        edges.push_back({v, 0, 0});
    }

    int d[V], ptr[V];

    int C;

    bool bfs(int S, int T) {
        fill(d, d + N, inf);
        queue<int> q;
        d[S] = 0;
        q.push(S);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int i : g[v]) {
                const auto &[u, c, f] = edges[i];
                if (c >= f + C && d[u] > d[v] + 1) {
                    d[u] = d[v] + 1;
                    q.push(u);
                }
            }
        }
        return d[T] < inf;
    }

    int dfs(int v, int T, int w = inf) {
        if (v == T)
            return w;
        for (; ptr[v] < (int) g[v].size(); ptr[v]++) {
            int i = g[v][ptr[v]];
            const auto [u, c, f] = edges[i];
            if (c >= f + C && d[u] == d[v] + 1) {
                int delta = dfs(u, T, min((ll)w, c - f));
                if (delta) {
                    edges[i].f += delta;
                    edges[i ^ 1].f -= delta;
                    return delta;
                }
            }
        }
        return 0;
    }

    ll max_flow(int S, int T) {
        ll flow = 0;
        for (C = inf; C; C >>= 1)
            while (bfs(S, T)) {
                fill(ptr, ptr + N, 0);
                while (ll f = dfs(S, T))
                    flow += f;
            }
        return flow;
    }

    MAX_FLOW() {}

    void clear() {
        edges.clear();
        for (int i = 0; i < N; i++)
            g[i].clear();
    }

    MAX_FLOW(int _N) {
        N = _N;
        clear();
    }
};

const int maxN = 12e5 + 2;

MAX_FLOW<maxN> max_flow;

inline void solve() {
    int n, m;
    cin >> n >> m;
    vector a(n, vector<ll>(m));
    vector b(n, vector<ll>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> b[i][j];
    bool flag = true;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (a[i][j] != b[i][j])
                flag = false;
    if (flag) {
        cout << 0 << '\n';
        return;
    }
    ll sum = 0;
    for (int i = 0; i < n; i++)
        sum += accumulate(all(a[i]), 0ll);
    int lo = 0, hi = n + m - 2;
    vector<pii> nna, nnb;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (a[i][j])
                nna.push_back({i, j});
            if (b[i][j])
                nnb.push_back({i, j});
        }
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        max_flow.clear();
        int k = mid - 2;
        /*if (k > 2)
            max_flow.N = 4 * n * m + 2;
        else*/
            max_flow.N = 2 * n * m + 2;
        int S = max_flow.N - 2;
        int T = S + 1;
        max_flow.clear();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                int v = i * m + j;
                if (a[i][j])
                    max_flow.add_edge(S, v, a[i][j]);
                if (b[i][j])
                    max_flow.add_edge(v + n * m, T, b[i][j]);
            }
        /*if (k > 2) {
            vector<int> L, R;
            auto pushR = [&](int v) {
                max_flow.add_edge(v + 2 * n * m, v + n * m, linf);
                if (!R.empty())
                    max_flow.add_edge(v + 2 * n * m, R.back() + 2 * n * m, linf);
                R.push_back(v);
            };
            auto pushL = [&](int v) {
                max_flow.add_edge(v + 3 * n * m, v + n * m, linf);
                if (!L.empty())
                    max_flow.add_edge(v + 3 * n * m, L.back() + 3 * n * m, linf);
                L.push_back(v);
            };
            auto pop = [&]() {
                if (L.empty())
                    for (; !R.empty(); R.pop_back())
                        pushL(R.back());
                L.pop_back();
            };
            auto topL = [&]() {
                return L.empty() ? -1 : L.back() + 3 * n * m;
            };
            auto topR = [&]() {
                return R.empty() ? -1 : R.back() + 2 * n * m;
            };
            for (int i = 0; i < n; i++) {
                L.clear();
                R.clear();
                for (int j = 0; j < m && j < k; j++)
                    pushR(i * m + j);
                for (int j = 0; j < m; j++) {
                    if (j + k < m)
                        pushR(i * m + j + k);
                    if (j - k - 1 >= 0)
                        pop();
                    for (int di = 0; di < n; di++) {
                        int v = di * m + j;
                        int u = topL();
                        if (u != -1)
                            max_flow.add_edge(v, u, linf);
                        u = topR();
                        if (u != -1)
                            max_flow.add_edge(v, u, linf);
                    }
                }
            }
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++) {
                    int v = i * m + j;
                    for (int di = 0; di < n; di++) {
                        for (int dj = -mid + abs(i - di); dj <= -k; dj++)
                            if (dj >= 0) {
                                int u = di * m + dj;
                                max_flow.add_edge(v, u, linf);
                            }
                        for (int dj = k; dj <= mid - abs(i - di); dj++)
                            if (dj < m) {
                                int u = di * m + dj;
                                max_flow.add_edge(v, u, linf);
                            }
                    }
                }
        } else {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    for (int di = max(0, i - mid); di <= min(n - 1, i + mid); di++)
                        for (int dj = max(0, j - mid); dj <= min(m - 1, j + mid); dj++)
                            if (abs(di - i) + abs(dj - j) <= mid)
                                max_flow.add_edge(i * m + j, n * m + di * m + dj, inf);
        }*/
        for (auto [i, j] : nna)
            for (auto [di, dj] : nnb)
                if (abs(i - di) + abs(j - dj) <= mid)
                    max_flow.add_edge(i * m + j, n * m + di * m + dj, inf);
        ll flow = max_flow.max_flow(S, T);
        if (flow == sum)
            hi = mid;
        else
            lo = mid;
    }
    cout << hi << '\n';
}

signed main() {
#ifdef _DEBUG
    freopen("01.dat", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt = 1;
    cin >> tt;
    for (int test_id = 1; test_id <= tt; test_id++) {
#ifdef _DEBUG
        cout << "Case #" << test_id << ":\n";
#endif
        solve();
    }
    return 0;
}
