#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.rbegin(), v.rend());
	deque <int> q(v.begin(), v.end());
	int ans[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int ds = i + j;
			if (ds % 2 == 0) {
				ans[i][j] = q.front();
				q.pop_front();
			}
			else {
				ans[i][j] = q.back();
				q.pop_back();
			}
		}
	}
	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();
	}
}