#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
using namespace std;
 
const int N = 151;
const int Inf = 2147483641;
struct Node{int to,C,val,facx,facy,next;}E[N*N*2];
struct Point{int x,y;};
int n,A[N][N],B[N][N],head[N],tot,far[N],in[N],up[N],Ans,S,T;
 
inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
 
inline int Cross(Point a,Point b,Point c){
  return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
 
inline void link(int u,int v,int c,int val,int fca,int fcb){
  E[++tot]=(Node){v,c,val,fca,fcb,head[u]};
  head[u]=tot;
  E[++tot]=(Node){u,0,-val,-fca,-fcb,head[v]};
  head[v]=tot;
}
 
inline bool SPFA(Point &ans){
  memset(far,127/3,sizeof(far));
  memset(up,0,sizeof(up));
  queue<int>Q;Q.push(S);far[S]=0;
  int fx=0,fy=0;
  while(!Q.empty()){
    int x=Q.front();Q.pop();in[x]=0;
    for(int e=head[x];e;e=E[e].next){
      int y=E[e].to;
      if(E[e].C<=0 || far[x]+E[e].val>=far[y])
        continue;
      far[y]=far[x]+E[e].val,up[y]=e;
      if(!in[y])Q.push(y),in[y]=1;
    }
  }
  if(!up[T])return false;
  for(int i=T;i!=S;i=E[up[i]^1].to){
    fx+=E[up[i]].facx,fy+=E[up[i]].facy;
    E[up[i]].C--;E[up[i]^1].C++;
  }
  ans.x+=fx;ans.y+=fy;return true;
}
 
inline Point fyl(){
  Point ans=(Point){0,0};
  while(SPFA(ans));
  Ans=min(Ans,ans.x*ans.y);
  return ans;
}
 
inline Point getp(int xv,int yv){
  memset(head,0,sizeof(head));tot=1;
  for(int i=1;i<=n;++i){
    link(S,i,1,0,0,0);
    for(int j=1;j<=n;++j)
      link(i,j+n,1,xv*A[i][j]+yv*B[i][j],A[i][j],B[i][j]);
    link(i+n,T,1,0,0,0);
  }
  return fyl();
}
 
inline void solve(Point Pa,Point Pb){
  Point mid=getp(Pa.y-Pb.y,Pb.x-Pa.x);
  if(Cross(Pb,Pa,mid)>0)
    solve(Pa,mid),solve(mid,Pb);
}
 
int main()
{
  /*freopen(".in","r",stdin);
    freopen(".out","w",stdout);*/
  int Case=gi();
  while(Case--){
    n=gi();Ans=Inf;S=0;T=2*n+1;
    for(int i=1;i<=n;++i)
      for(int j=1;j<=n;++j)
        A[i][j]=gi();
    for(int i=1;i<=n;++i)
      for(int j=1;j<=n;++j)
        B[i][j]=gi();
    if(n==1){
      printf("%d\n",A[1][1]*B[1][1]);
      continue;
    }
    Point Pa=getp(1,0),Pb=getp(0,1);
    solve(Pa,Pb);
    printf("%d\n",Ans);
  }
  /*fclose(stdin);
    fclose(stdout);*/
  return 0;
}

https://www.luogu.com.cn/record/131465061 AC记录