#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 10

int grid[MAXX][MAXX];
int dp[1<<MAXX][1<<MAXX];
int N;

int rec(int alice, int bob)
{

    int &ret = dp[alice][bob];

    if(ret != -1) return ret;


    ret = -INF;

    loop(i, N)
    {
        if( !(alice & (1<<i)) )
        {
            loop(j, N)
            {
                if( ! (bob & (1<<j)) )
                {
                    ret = max(ret,  grid[i][j] + rec((alice | 1<<i), (bob | 1<<j)) );
                }
            }
        }
    }
    return ret;

}


int main()
{
    int kases;
    getint(kases);

    while(kases--)
    {
        getint(N);
        loop(i, N)
        {
            loop(j, N)
            {
                getint(grid[i][j]);
            }
        }

        mem(dp, -1);

        dp[1<<N - 1][1<<N - 1] = 0;

        pf("%d\n", -rec(0, 0));

    }

    return 0;
}