#include <bits/stdc++.h>
using namespace std;
#define rep(i, u) for (int i = fir[u]; i; i = e[i].nxt)
int read()
{
int x = 0, f = 1; char ch = getchar();
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
const int inf = 50000000;
int T, n, ans, a[73][73], b[73][73];
struct Vector
{
int x, y;
Vector() {}
Vector(int xx, int yy) { x = xx, y = yy; }
friend Vector operator - (Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }
friend int operator * (Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
};
struct Graph
{
int g[73][73], lx[73], ly[73], sla[73], match[73];
bool visx[73], visy[73];
void build(int wx, int wy)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = -(wx * a[i][j] + wy * b[i][j]);
}
bool dfs(int u)
{
visx[u] = true;
for (int v = 1; v <= n; v++) if (!visy[v])
{
int t = lx[u] + ly[v] - g[u][v];
if (!t)
{
visy[v] = 1;
if (!match[v] || dfs(match[v]))
{
match[v] = u;
return true;
}
}
else sla[v] = min(sla[v], t);
}
return false;
}
Vector km()
{
memset(lx, 0, sizeof lx);
memset(ly, 0, sizeof ly);
memset(match, 0, sizeof match);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
lx[i] = max(lx[i], g[i][j]);
for (int i = 1; i <= n; i++)
{
memset(sla, 63, sizeof sla);
while (true)
{
memset(visx, 0, sizeof visx);
memset(visy, 0, sizeof visy);
if (dfs(i)) break;
int d = inf;
for (int i = 1; i <= n; i++)
if (!visy[i]) d = min(d, sla[i]);
for (int i = 1; i <= n; i++)
if (visx[i]) lx[i] -= d;
for (int i = 1; i <= n; i++)
if (visy[i]) ly[i] += d;
else sla[i] -= d;
}
}
Vector re(0, 0);
for (int i = 1; i <= n; i++)
re.x += a[match[i]][i], re.y += b[match[i]][i];
return re;
}
} g;
void solve(Vector A, Vector B)
{
g.build(A.y - B.y, B.x - A.x);
Vector C = g.km();
ans = min(ans, C.x * C.y);
if ((B - A) * (C - A) >= 0) return;
solve(A, C), solve(C, B);
}
int main()
{
T = read();
while (T--)
{
n = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
b[i][j] = read();
g.build(1, 0);
Vector A = g.km();
g.build(0, 1);
Vector B = g.km();
ans = min(A.x * A.y, B.x * B.y);
solve(A, B);
printf("%d\n", ans);
}
return 0;
}
