#include <bits/stdc++.h>

struct Flow {
    struct Edge {
        int to, to_id;
        int64_t flow, capacity;
    };

    struct FlowGr {
        struct EdgeInfo {
            int u, v;
            int64_t capacity;
            bool directed;

            int a, b;
        };

        bool built = false;
        std::vector<int> cnt;
        std::vector<EdgeInfo> edges;
        std::vector<Edge> data;

        FlowGr() { ; }
        FlowGr(int n) : cnt(n + 1) {}

        std::pair<int, int> add_edge(int u, int v, int64_t capacity, bool directed) {
            assert(!built);
            int a = cnt[u]++;
            int b = cnt[v]++;
            edges.push_back({u, v, capacity, directed, a, b});
            return {u, a};
        }

        void build() {
            if (!built) {
                built = true;
                std::exclusive_scan(cnt.begin(), cnt.end(), cnt.begin(), 0);
                data.resize(cnt.back());
                for (auto [u, v, capacity, directed, a, b] : edges) {
                    data[cnt[u] + a] = Edge(v, b, 0, capacity);
                    data[cnt[v] + b] = Edge(u, a, capacity * directed, capacity);
                }
            }
        }

        std::span<Edge> operator[](size_t ind) {
            return std::span<Edge>(data.data() + cnt[ind], data.data() + cnt[ind + 1]);
        }
    };

    int n, S, T;
    int64_t flow;
    // std::vector<std::vector<Edge>> gr;
    FlowGr gr;
    std::vector<int> dist, used, deque;
    int64_t thr;

    Flow() = default;
    Flow(int n, int S, int T) : n(n), S(S), T(T), flow(0), gr(n), dist(n, -1), used(n, -1), deque(n, -1), thr(1) {}

    std::pair<int, int> add_edge(int u, int v, int64_t capacity, bool directed = true) {
        // int a = gr[u].size(), b = gr[v].size();
        // gr[u].push_back(Edge(v, b, 0, capacity));
        // gr[v].push_back(Edge(u, a, capacity * directed, capacity));
        // return {u, a};
        return gr.add_edge(u, v, capacity, directed);
    }

    bool run_bfs() {
        dist.assign(n, n);
        dist[S] = 0;
        int deque_begin = 0, deque_end = 0;
        deque[deque_end++] = S;
        while (deque_begin < deque_end) {
            int v = deque[deque_begin++];
            for (auto e : gr[v]) {
                if (int64_t cp = e.capacity - e.flow; cp >= thr && dist[e.to] == n) {
                    dist[e.to] = dist[v] + 1;
                    deque[deque_end++] = e.to;
                }
            }
        }
        return dist[T] != n;
    }

    void push(Edge& e, int64_t dlt) {
        e.flow += dlt;
        gr[e.to][e.to_id].flow -= dlt;
    }

    int64_t dfs(int v, int64_t min) {
        if (v == T || min == 0) {
            return min;
        }
        int64_t res = 0;
        for (int& i = used[v]; i < gr[v].size(); i++) {
            Edge& e = gr[v][i];
            if (int64_t cp = e.capacity - e.flow; cp >= thr && dist[e.to] == dist[v] + 1) {
                if (int64_t val = dfs(e.to, std::min<int64_t>(min, cp)); val) {
                    push(e, val), min -= val, res += val;
                    if (min < thr) {
                        break;
                    }
                }
            }
        }
        return res;
    }

    void find_max_flow() {
        // int64_t sum = 0;
        // std::cerr << gr.size() << "\n";
        // for (auto& i : gr) {
        //     sum += i.size();
        // }
        // std::cerr << sum << "\n";

        gr.build();
        while (run_bfs()) {
            used.assign(n, 0);
            flow += dfs(S, 1e18);
        }
    }

    void find_max_flow_scaling() {
        for (int i = 28; i >= 0; i -= 4) {
            thr = 1 << i;
            find_max_flow();
        }
    }
};

int solve_n1(std::vector<int64_t> a, std::vector<int64_t> b) {
    int n = a.size();
    std::vector<int64_t> prf_a(n + 1), prf_b(n + 1);
    for (int i = 0; i < n; i++) {
        prf_a[i + 1] = prf_a[i] + a[i];
        prf_b[i + 1] = prf_b[i] + b[i];
    }

    auto get = [&](auto& vec, int ind) -> int64_t {
        if (ind < 0) {
            return 0;
        }
        if (vec.size() <= ind) {
            return vec.back();
        }
        return vec[ind];
    };

    auto check = [&](int d) {
        int64_t max = -1e18;
        for (int i = 0; i <= n; i++) {
            max = std::max(max, -get(prf_a, i) + get(prf_b, i - d));
            int64_t val = get(prf_a, i) - get(prf_b, i + d);
            if (max + val > 0) {
                return false;
            }
        }
        return true;
    };

    int beg = -1, end = n;
    while (beg + 1 < end) {
        int mid = (beg + end) / 2;
        (check(mid) ? end : beg) = mid;
    }

    return end;
}

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n * m), b(n * m);
    for (auto& i : a) std::cin >> i;
    for (auto& i : b) std::cin >> i;

    const int64_t total = std::accumulate(a.begin(), a.end(), 0ll);

    auto check = [&](int d) {
        int sz = std::bit_ceil<size_t>(m);
        Flow fl(2 + 2 * n * m + 2 * sz, 0, 1);
        for (int i = 0; i < n * m; i++) {
            fl.add_edge(0, 2 + i, a[i]);
        }
        for (int i = 0; i < n * m; i++) {
            fl.add_edge(2 + n * m + i, 1, b[i]);
        }
        for (int i = 2 * sz - 1; i > 1; i--) {
            fl.add_edge(2 + 2 * n * m + i / 2, 2 + 2 * n * m + i, 1e18);
        }
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                fl.add_edge(2 + 2 * n * m + sz + i, 2 + n * m + j * m + i, 1e18);
            }
        }
        auto add_segment = [&](int v, int l, int r) {
            for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
                if (l & 1) {
                    fl.add_edge(v, 2 + 2 * n * m + l++, 1e18);
                }
                if (r & 1) {
                    fl.add_edge(v, 2 + 2 * n * m + --r, 1e18);
                }
            }
        };

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                add_segment(2 + i * m + j, std::clamp(j - d + (n - 1), 0, j + 1), std::clamp(j + d - (n - 1) + 1, j + 1, m));

                auto add = [&](int x, int y) {
                    if (0 <= y && y < m && std::abs(i - x) + std::abs(j - y) <= d) {
                        fl.add_edge(2 + i * m + j, 2 + n * m + x * m + y, 1e18);
                    }
                };
                for (int x = 0; x < n; x++) {
                    for (int dy = 0; dy < n - 1; dy++) {
                        add(x, j - d + dy);
                        add(x, j + d - dy);
                    }
                }
            }
        }

        fl.find_max_flow();
        // fl.find_max_flow_scaling();
        int64_t f = fl.flow;
        return f == total;
    };

    std::vector<int64_t> A(m), B(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            A[j] += a[i * m + j];
            B[j] += b[i * m + j];
        }
    }

    int x = solve_n1(A, B);

    int beg = x - 1, end = x + (n - 1);
    while (beg + 1 < end) {
        int mid = (beg + end) / 2;
        (check(mid) ? end : beg) = mid;
    }
    std::cout << end << "\n";
}

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
        std::cout.flush();
        // break;
    }

    return 0;
}