#include <bits/stdc++.h>
using namespace std;
#define ll long long

void solve() {
	int n, m; cin >> n >> m;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int x; cin >> x;
			v.push_back(x);
		}
	}
	sort(v.begin(), v.end());
	deque <int> q(v.begin(), v.end());
	int ans[n][m];
	queue <array<int, 2>> pq;
	pq.push({0, 0});
	int used[n][m] {};
	used[0][0] = 1;

	while (!pq.empty()) {
		auto [x, y] = pq.front();
		pq.pop();
		if ((x + y) % 2 == 0) {
			ans[x][y] = q.front();
			q.pop_front();
		}
		else {
			ans[x][y] = q.back();
			q.pop_back();
		}
		if (y + 1 < m and !used[x][y + 1]) pq.push({x, y + 1}), used[x][y + 1] = 1;
		if (x + 1 < n and !used[x + 1][y]) {
			pq.push({x + 1, y});
			used[x + 1][y] = 1;
		}
	}

	int a = 1e9;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i + 1 < n) a = min(a, ans[i + 1][j] + ans[i][j]);
			if (j + 1 < m) a = min(a, ans[i][j + 1] + ans[i][j]);
		}
	}
	cout << a << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int tt = 1;
	cin >> tt;
	while (tt--) {
		solve();
	}
}