#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n,mat[N][N],dp[N][(1<<N) +5];

int solve(int row, int col, int mask){
    if(dp[row][mask]!=-1 )return dp[row][mask];
    ////////////////////////////////
    if(row==n){
        if(n==1)return mat[row][col];
        for(int i=1; i<=n ;i++) if((mask&(1<<(i-1)))==0)return mat[row][i];
    }
    ////////////////////////////////
    int best = 0,bc=0,pre=0;
    for(int i=1; i<=n; i++){
        if((mask & (1<<(i-1))) == 0){
            pre = best;
            best = max(best, solve(row+1,i,mask | (1<<(i-1))));
        }
    }
    return dp[row][mask]=(best+mat[row][col]);
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t;
    scanf("%d",&t);
    while(t--){
        int i,j;
        memset(dp, -1, sizeof dp);
        scanf("%d",&n);
        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++){
                scanf("%d",&mat[i][j]);
            }
        }
        int ans = 0,mask;
        for(i=1; i<=n; i++){
            mask = 1<<(i-1);
            ans = max(ans,solve(1,i,mask));
        }
        cout<<ans<<"\n";
    }
    return 0;
}