#include <bits/stdc++.h>

template <typename T>
void chmax(T& val, const T& upd) { val = std::max(val, upd); }

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

template <int n>
constexpr auto gen_masks() {
    if constexpr (n == 1) {
        std::array<std::array<int, 1>, 1> res;
        res[0][0] = 0;
        return res;
    } else {
        auto mk = gen_masks<n - 1>();
        std::array<std::array<int, n>, mk.size() * 3> res;
        for (int i = 0; i < mk.size(); i++) {
            for (int k = -1; k <= 1; k++) {
                std::copy(mk[i].begin(), mk[i].end(), res[3 * i + (k + 1)].begin());
                res[3 * i + (k + 1)].back() = mk[i].back() + k;
            }
        }
        for (auto& vec : res) {
            int min = *std::min_element(vec.begin(), vec.end());
            std::for_each(vec.begin(), vec.end(), [&](int& x) { x -= min; });
        }
        return res;
    }
}

template <int n>
int solve(int m, std::vector<int64_t> a, std::vector<int64_t> b) {
    std::vector<int64_t> prf_b(n * m + 1);
    for (int i = 0; i < n * m; i++) {
        prf_b[i + 1] = prf_b[i] + b[i];
    }
    std::vector<int64_t> prf_B(m + 1);
    for (int i = 0; i < m; i++) {
        prf_B[i + 1] = prf_B[i];
        for (int j = 0; j < n; j++) {
            prf_B[i + 1] += b[j * m + i];
        }
    }

    constexpr auto masks = gen_masks<n>();
    constexpr size_t k = masks.size();

    std::vector<int> min_dist(k * k);
    for (int mk1 = 0; mk1 < k; mk1++) {
        for (int mk2 = 0; mk2 < k; mk2++) {
            int max = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    max = std::max(max, std::abs(masks[mk1][i] - masks[mk2][j]) - std::abs(i - j));
                }
            }
            min_dist[mk1 * k + mk2] = max;
        }
    }

    auto check = [&](int D) -> bool {
        auto get1 = [&](int l, int r) -> int64_t {
            return prf_B[r] - prf_B[l];
        };
        auto get2 = [&](int j, int l, int r) -> int64_t {
            return prf_b[j * m + r] - prf_b[j * m + l];
        };

        std::vector<std::array<int64_t, k>> dp(m), dlt_r(m);

        for (int i = 0; i < m; i++) {
            for (int mk = 0; mk < k; mk++) {
                int64_t val = 0, dlt = 0;
                for (int j = 0; j < n; j++) {
                    val += a[j * m + i] * (masks[mk][j] == 0);
                    val -= get2(j, std::clamp(i - (D - masks[mk][j]), 0, i + 1), i + 1);
                    dlt -= get2(j, i + 1, std::clamp(i + (D - masks[mk][j]) + 1, i + 1, m));
                }
                dp[i][mk] = val, dlt_r[i][mk] = dlt;
            }
        }

        auto meow = [&](int i, int i2, bool skip = false) {
            for (int mk = 0; mk < k; mk++) {
                int64_t val = dp[i][mk];
                for (int mk2 = 0; mk2 < k; mk2++) {
                    // left 1 4 5
                    // const int xxx = 1;

                    std::array ar = {1, 4, 5};
                    if ((skip || 0) && (std::count(ar.begin(), ar.end(), mk) || std::count(ar.begin(), ar.end(), mk2))) {
                        continue;
                    }

                    // if ((skip || 0) && (mk == xxx || mk2 == xxx)) {
                    //     continue;
                    // }

                    if (i2 - i < min_dist[mk * k + mk2]) {
                        continue;
                    }
                    int64_t dlt = 0;
                    for (int j = 0; j < n; j++) {
                        int l = std::clamp(i + (D - masks[mk][j]) + 1, i + 1, i2 + 1);
                        int r = std::clamp(i2 - (D - masks[mk2][j]), l, i2 + 1);
                        dlt += a[j * m + i2] * (masks[mk2][j] == 0);
                        dlt -= get2(j, i + 1, l) + get2(j, r, i2 + 1);
                    }
                    chmax(dp[i2][mk2], val + dlt);
                }
            }
        };

        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j <= i + 1 && j < m; j++) {
                meow(i, j, false);
            }

            int r = i + 2 * D;
            int l = std::max(i + 1,
                             r - (n - 1));
            l = std::max(i + 1, l);
            for (int j = l; j <= r && j < m; j++) {
                meow(i, j, true);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int mk = 0; mk < k; mk++) {
                if (int64_t d = dp[i][mk] + dlt_r[i][mk]; d > 0) {
                    return false;
                }
            }
        }
        return true;
    };

    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;
    }
    return end;
}

template <size_t scale, size_t... S, typename Functor>
__attribute__((always_inline)) constexpr void static_foreach_seq(Functor function, std::index_sequence<S...>) {
    ((function(std::integral_constant<size_t, S * scale>())), ...);
}

template <size_t Size, size_t scale = 1, typename Functor>
__attribute__((always_inline)) constexpr void static_for(Functor functor) {
    return static_foreach_seq<scale>(functor, std::make_index_sequence<Size>());
}

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

    static_for<5>([&](auto i) {
        if (i + 1 == n) {
            int ans = solve<i + 1>(m, a, b);
            std::cout << ans << "\n";
        }
    });
}

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

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}