#include<bits/stl_algobase.h>
#include<ctype.h>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
#include<cassert>
using namespace std;
const int N = 5e4 + 10;
const int V = 3e4;
const int K = 4;
const int INF = 0x3f3f3f3f;
const char endl = '\n';
namespace io {
struct istream {
char ch;
inline istream &operator>>(int &x) {
while(!isdigit(ch = getchar()));
x = ch - '0';
while(isdigit(ch = getchar())) x = x * 10 + ch - '0';
return *this;
}
} cin;
struct ostream {
char buf[60], top;
inline ostream() : top(0) {}
inline ostream &operator<<(char c) {
putchar(c);
return *this;
}
inline ostream &operator<<(const char s[]) {
for(int i = 0; s[i]; i++) putchar(s[i]);
return *this;
}
inline ostream &operator<<(int x) {
if(x < 0) putchar('-'), x = -x;
do buf[++top] = x % 10, x /= 10; while(x);
while(top) putchar(buf[top--] + '0');
return *this;
}
} cout;
}
using io::cin;
using io::cout;
int T, k;
int n;
int a[N][K + 3];
namespace simple {
void work1() {
int mn = INF, mx = 0;
for(int i = 1; i <= n; i++) mn = min(mn, a[i][1]);
for(int i = 1; i <= n; i++) mx = max(mx, a[i][1]);
cout << mx - mn << '\n';
}
void work2() {
int mn1 = INF, mn2 = INF, mx1 = 0, mx2 = 0;
for(int i = 1; i <= n; i++) if(a[i][1] > a[i][2]) swap(a[i][1], a[i][2]);
for(int i = 1; i <= n; i++) mn1 = min(mn1, a[i][1]);
for(int i = 1; i <= n; i++) mx1 = max(mx1, a[i][1]);
for(int i = 1; i <= n; i++) mn2 = min(mn2, a[i][2]);
for(int i = 1; i <= n; i++) mx2 = max(mx2, a[i][2]);
cout << max(mx1 - mn1, mx2 - mn2) << '\n';
}
}
int mn, mx, ans;
namespace k3 {
struct Op {
int v, w, col;
inline bool operator<(const Op &b) const {
if(v != b.v) return v < b.v;
return w < b.w;
}
};
inline void rotate(int a[], int p) {
if(p == 2) swap(a[1], a[2]), swap(a[2], a[3]);
else if(p == 3) swap(a[2], a[3]), swap(a[1], a[2]);
}
int kp;
int lock[5];
int cnt[N], cc;
vector<Op> op;
void add_Line(int l, int r, int col) {
op.push_back({l, 1, col});
op.push_back({r + 1, -1, col});
}
bool check(int mid) {
op.clear();
for(int i = 1; i <= n; i++) {
if(i <= 2 && lock[i]) {
if(a[i][1] - mn > mid) return false;
if(mx - a[i][5 - kp] > mid) return false;
add_Line(a[i][kp] - mid, a[i][kp], i);
continue;
}
for(int j = 1; j <= 3; j++, rotate(a[i], 3)) {
if(a[i][1] - mn > mid) continue;
if(mx - a[i][5 - kp] > mid) continue;
add_Line(a[i][kp] - mid, a[i][kp], i);
}
}
sort(op.begin(), op.end());
bool flag = false;
for(Op &o : op) {
if(cnt[o.col] == 0 && o.w == 1) ++cc;
if(cnt[o.col] == 1 && o.w == -1) --cc;
cnt[o.col] += o.w;
if(cc == n) flag = true;
}
return flag;
}
void calc() {
int l = 0, r = V + 5;
while(l < r) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
ans = min(ans, l);
}
void work3() {
ans = INF;
lock[1] = lock[2] = 0;
mn = INF, mx = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
}
}
for(int i = 1; i <= n && a[1][1] != mn; i++) {
for(int j = 1; j <= k; j++) {
if(a[i][j] == mn) {
rotate(a[i], j);
swap(a[i], a[1]);
break;
}
}
}
if(a[1][2] == mx || a[1][3] == mx) {
if(a[1][2] == mx) kp = 3;
else kp = 2;
lock[1] = 1;
calc();
cout << ans << '\n';
return;
}
for(int i = 2; i <= n && a[2][1] != mx; i++) {
for(int j = 1; j <= k; j++) {
if(a[i][j] == mx) {
rotate(a[i], j);
swap(a[i], a[2]);
break;
}
}
}
lock[1] = lock[2] = 1;
rotate(a[2], 3);
kp = 3;
calc();
rotate(a[2], 3);
kp = 2;
calc();
cout << ans << '\n';
}
}
namespace k4 {
namespace SegT {
int mx[4 * V], tag[4 * V];
inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }
inline void push_up(int p) { mx[p] = max(mx[lc(p)], mx[rc(p)]); }
inline void move_tag(int p, int tg) {
mx[p] += tg;
tag[p] += tg;
}
void push_down(int p) {
if(!tag[p]) return;
move_tag(lc(p), tag[p]);
move_tag(rc(p), tag[p]);
tag[p] = 0;
}
void add(int p, int l, int r, int ql, int qr, int v) {
if(ql <= l && r <= qr) { move_tag(p, v); return; }
push_down(p);
int mid = (l + r) >> 1;
if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
push_up(p);
}
int query() { return mx[1]; }
}
inline void rotate(int a[], int p) {
if(p == 1) return;
if(p == 2) swap(a[1], a[2]), swap(a[2], a[3]), swap(a[3], a[4]);
else if(p == 3) swap(a[1], a[3]), swap(a[2], a[4]);
else swap(a[3], a[4]), swap(a[2], a[3]), swap(a[1], a[2]);
}
struct Op3 {
int x, w;
inline bool operator<(const Op3 &b) const {
if(x != b.x) return x < b.x;
return w < b.w;
}
};
struct Op4 {
int x, y1, y2, w;
inline bool operator<(const Op4 &b) const {
if(x != b.x) return x < b.x;
return w < b.w;
}
};
multiset<Op3> op3;
vector<Op4> op34, op4;
void add_Rec(int x, int y, int d) {
op34.push_back({max(1, x - d), max(1, y - d), y, 1});
op34.push_back({x + 1, max(1, y - d), y, -1});
}
void enter() {
sort(op34.begin(), op34.end());
int prex = -1;
for(Op4 &o : op34) {
if(~prex && o.x > prex) {
int cnt = 0, prey;
for(const Op3 &o2 : op3) {
if(o2.w == 1 && cnt == 0) prey = o2.x;
if(o2.w == -1 && cnt == 1) {
op4.push_back({prex, prey, o2.x - 1, 1});
op4.push_back({o.x, prey, o2.x - 1, -1});
}
cnt += o2.w;
}
}
prex = o.x;
if(o.w == 1) {
op3.insert({o.y1, 1});
op3.insert({o.y2 + 1, -1});
} else {
op3.erase(op3.find({o.y1, 1}));
op3.erase(op3.find({o.y2 + 1, -1}));
}
}
if(!op3.empty()) throw;
op34.clear();
}
int lock[5];
int mxp, ans;
bool check(int mid) {
op4.clear();
for(int i = 1; i <= n; i++) {
if(i <= 2 && lock[i]) {
if(a[i][1] - mn > mid) return false;
if(mx - a[i][mxp] > mid) return false;
if(mxp == 2) add_Rec(a[i][3], a[i][4], mid);
else if(mxp == 3) add_Rec(a[i][2], a[i][4], mid);
else add_Rec(a[i][2], a[i][3], mid);
enter();
continue;
}
for(int j = 1; j <= 4; j++, rotate(a[i], 4)) {
if(a[i][1] - mn > mid) continue;
if(mx - a[i][mxp] > mid) continue;
if(mxp == 2) add_Rec(a[i][3], a[i][4], mid);
else if(mxp == 3) add_Rec(a[i][2], a[i][4], mid);
else add_Rec(a[i][2], a[i][3], mid);
}
enter();
}
sort(op4.begin(), op4.end());
bool flag = false;
for(Op4 &o : op4) {
SegT::add(1, 1, V, o.y1, o.y2, o.w);
if(SegT::query() >= n) flag = true;
}
return flag;
}
void calc() {
op4.clear();
int l = 0, r = V + 5;
while(l < r) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
ans = min(ans, l);
}
void work4() {
ans = INF;
mn = INF, mx = 0;
lock[1] = lock[2] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
}
}
for(int i = 1; i <= n && a[1][1] != mn; i++) {
for(int j = 1; j <= k; j++) {
if(a[i][j] == mn) {
rotate(a[i], j);
swap(a[1], a[i]);
break;
}
}
}
if(a[1][2] == mx || a[1][3] == mx || a[1][4] == mx) {
if(a[1][2] == mx) mxp = 2;
else if(a[1][3] == mx) mxp = 3;
else mxp = 4;
lock[1] = 1;
calc();
cout << ans << '\n';
return;
}
for(int i = 2; i <= n; i++) {
for(int j = 1; j <= k; j++) {
if(a[i][j] == mx) {
rotate(a[i], j);
swap(a[2], a[i]);
break;
}
}
}
lock[1] = lock[2] = 1;
rotate(a[2], 4);
mxp = 2;
calc();
rotate(a[2], 4);
mxp = 3;
calc();
rotate(a[2], 4);
mxp = 4;
calc();
cout << ans << '\n';
}
}
using simple::work1;
using simple::work2;
using k3::work3;
using k4::work4;
int main() {
cin >> T >> k;
while(T--) {
cin >> n;
for(int j = 1; j <= k; j++) {
for(int i = 1; i <= n; i++) {
cin >> a[i][j];
}
}
if(k == 1) work1();
else if(k == 2) work2();
else if(k == 3) work3();
else if(k == 4) work4();
}
return 0;
}