#include <bits/stdc++.h>

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

struct Vector {
    int x, y;

    Vector() : x(0), y(0) { ; }
    Vector(int x, int y) : x(x), y(y) { ; }

    Vector operator+(const Vector& other) const { return Vector(x + other.x, y + other.y); };
    Vector operator-(const Vector& other) const { return Vector(x - other.x, y - other.y); };

    int m_abs() const { return std::abs(x) + std::abs(y); }
};

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

int solve_n2(std::vector<int64_t> a, std::vector<int64_t> b) {
    const int n = 2;
    const int m = a.size() / 2;

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

    auto get = [&](const auto& prf, int l, int r) {
        return prf[r] - prf[l];
    };
    auto get2 = [&](const auto& prf, int x1, int x2, int y1, int y2) {
        int64_t res = 0;
        for (int i = x1; i < x2; i++) {
            res += get(prf, i * m + y1, i * m + y2);
        }
        return res;
    };

    auto check = [&](int D) -> bool {
        std::vector<std::array<int64_t, 4>> dp(m), dlt_r(m);

        for (int i = 0; i < m; i++) {
            dp[i].fill(-1e18);
            for (int mask = 1; mask < 4; mask++) {
                int64_t val = 0;
                int64_t dlt = 0;

                for (int j = 0; j < 2; j++) {
                    if (mask >> j & 1) {
                        val += a[j * m + i];
                    }
                }
                val -= get2(prf_b, 0, 2, std::max(0, i - D + 1), i + 1);
                if (int y = i - D; y >= 0) {
                    for (int j = 0; j < 2; j++) {
                        if (mask >> j & 1) {
                            val -= b[j * m + y];
                        }
                    }
                }

                dlt -= get2(prf_b, 0, 2, i + 1, std::min(m, std::max(i + 1, i + D)));
                if (int y = i + D; i < y && y < m) {
                    for (int j = 0; j < 2; j++) {
                        if (mask >> j & 1) {
                            dlt -= b[j * m + y];
                        }
                    }
                }

                dp[i][mask] = val;
                dlt_r[i][mask] = dlt;
            }
        }
        for (int i = 0; i < m - 1; i++) {
            for (int mask = 1; mask < 4; mask++) {
                for (int mask2 = 1; mask2 < 4; mask2++) {
                    int64_t dlt = 0;
                    for (int j = 0; j < 2; j++) {
                        if (mask2 >> j & 1) {
                            dlt += a[j * m + i + 1];
                        }
                        if (D > 0 || (mask2 >> j & 1)) {
                            dlt -= b[j * m + i + 1];
                        }
                    }
                    chmax(dp[i + 1][mask2], dp[i][mask] + dlt);
                }
            }
            if (D > 0) {
                for (int mask = 1; mask < 4; mask++) {
                    for (int i2 = i + 2 * D; i2 < m && i2 <= i + 2 * D; i2++) {
                        for (int mask2 = 1; mask2 < 4; mask2++) {
                            int64_t dlt = 0;
                            dlt -= get2(prf_b, 0, 2, i + 1, i + D);
                            dlt -= get2(prf_b, 0, 2, i + D + 1, i2 + 1);
                            for (int j = 0; j < 2; j++) {
                                if (mask2 >> j & 1) {
                                    dlt += a[j * m + i2];
                                }
                            }
                            for (int j = 0; j < 2; j++) {
                                if ((mask | mask2) >> j & 1) {
                                    dlt -= b[j * m + i + D];
                                }
                            }

                            chmax(dp[i2][mask2], dp[i][mask] + dlt);
                        }
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int mask = 1; mask < 4; mask++) {
                if (int64_t x = dp[i][mask] + dlt_r[i][mask]; x > 0) {
                    return false;
                }
            }
        }
        return true;
    };

    int beg = -1, end = m + 1;
    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<int64_t> a(n * m), b(n * m);
    for (auto& i : a) std::cin >> i;
    for (auto& i : b) std::cin >> i;

    if (n == 1) {
        int ans = solve_n1(a, b);
        std::cout << ans << "\n";
        return;
    }

    if (n != 2) {
        exit(52);
    }

    int ans = solve_n2(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();
        std::cout.flush();
        // break;
    }

    return 0;
}