#include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 int dp[][<<];///表示最大相亲的好感和

 void solve(int n,int a[][])

 {

     int w=<<n;

     memset(dp,,sizeof(dp));///清0，用0表示没有此状态

     for(int i=; i<n; i++)

     {

         dp[][<<i]=a[][i];///对于出状态进行预处理，即第一行的状态暴力一下

     }

     for(int i=; i<n-; i++)///第一层循环遍历0~n-1行

     {

         for(int j=; j<w; j++)///第二层循环遍历0~（1<<n）的状态

         {

             if(dp[i][j]!=)///对于非0的状态进行处理

                 for(int k=; k<n; k++)

                 {

                     if(!(j&(<<k)))///j里有1<<k的状态

                     {

                         if(dp[i+][j+(<<k)]<=dp[i][j]+a[i+][k])///求第i+1行的最大值

                             dp[i+][j+(<<k)]=dp[i][j]+a[i+][k];

                     }

                 }

         }

     }

     int ans=;

     for(int i=; i<w; i++)

     {

         if(ans<dp[n-][i])

             ans=dp[n-][i];///对于最后一行的状态遍历求dp

     }

     printf("%d\n",ans);

 }

 int main()

 {

     int a[][];

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int n;

         scanf("%d",&n);

         for(int i=; i<n; i++)

             for(int j=; j<n; j++)

             {

                 scanf("%d",&a[i][j]);

             }

         solve(n,a);

     }

 }