HDU6445

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1005;
const int M=N*3;
const int INF=0x3f3f3f3f;

int ecnt=1;
int fir[N];
int nex[M];
int from[M];
int to[M];
int f[M];
int w[M];

int tot,S,T;
int h[N];
int dis[N];
int lst[N];

inline bool dijkstra(){
    memset(dis+1,INF,tot<<2);
    priority_queue<pair<int,int> >Q;
    Q.push(make_pair(dis[S]=0,S));
    while(!Q.empty()){
        int d=-Q.top().first;
        int x=Q.top().second;
        Q.pop();
        if(dis[x]!=d)continue;
        for(int i=fir[x];i;i=nex[i]){
            int v=to[i];
            if(f[i]&&dis[v]>dis[x]+w[i]+h[x]-h[v]){
                lst[v]=i;
                dis[v]=dis[x]+w[i]+h[x]-h[v];
                if(dis[v]<dis[T]){
                    Q.push(make_pair(-dis[v],v));
                }
            }
        }
    }
    return dis[T]!=INF;
}

int MinCost,MaxFlow;

inline void MCMF(){
    MinCost=MaxFlow=0;
    while(dijkstra()){
        int flow=INF;
        for(int i=T,e;i!=S;i=from[e]){
            flow=min(flow,f[e=lst[i]]);
        }
        MaxFlow+=flow;
        MinCost+=flow*(dis[T]+h[T]-h[S]);
        for(int i=T,e;i!=S;i=from[e]){
            e=lst[i];
            f[e]-=flow;
            f[e^1]+=flow;
        }
        for(int i=1;i<=tot;++i){
            h[i]+=dis[i];
        }
    }
}

inline void addedge(int u,int v,int flow,int cost){
    nex[++ecnt]=fir[u],fir[u]=ecnt,from[ecnt]=u,to[ecnt]=v,f[ecnt]=flow,w[ecnt]=cost;
    nex[++ecnt]=fir[v],fir[v]=ecnt,from[ecnt]=v,to[ecnt]=u,f[ecnt]=0,w[ecnt]=-cost;
}

int deg[N];

inline void add(int e,int u,int v){
    addedge(S,e,1,0);
    addedge(e,u,1,0);
    addedge(e,v,1,0);
    addedge(u,T,1,deg[u]++);
    addedge(v,T,1,deg[v]++);
}

char s[N][N];

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int TestCase;r(TestCase);
    while(TestCase--){
        int n;r(n);
        for(int i=1;i<=n;++i){
            scanf("%s",s[i]+1);
            for(int j=1;j<=n;++j){
                if(s[i][j]=='1'){
                    deg[i]++;
                }
            }
        }
        tot=n;
        S=++tot;
        T=++tot;
        int sum=0;
        for(int i=1;i<=n;++i){
            sum+=deg[i]*(deg[i]-1)/2;
        }
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j){
                if(s[i][j]=='2'){
                    add(++tot,i,j);
                }
            }
        }
        MCMF();
        printf("%d\n",n*(n-1)*(n-2)*(n-3)-(n-3)*8*(sum+MinCost));
        memset(fir+1,0,tot<<2);
        memset(deg+1,0,n<<2);
        ecnt=1;
    }
}