#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("cast.in");
ofstream fout("cast.out");

const int inf = 1e16;

int32_t main()
{
  cin.tie(nullptr)->sync_with_stdio(false);
  int q;
  fin >> q;
  while (q--)
  {
    int n;
    fin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
    {
      for (int j = 0; j < n; ++j)
      {
        fin >> a[i][j];
      }
    }
    vector<vector<int>> dp((1 << n), vector<int>(n, inf));
    for (int i = 1; i < (1 << n); ++i)
    {
      int cnt = 0;
      for (int j = 0; j < n; ++j)
      {
        if (i & (1 << j))
        {
          cnt++;
        }
      }
      if (cnt == 1)
      {
        for (int j = 0; j < n; ++j)
        {
          if (i & (1 << j))
          {
            dp[i][j] = 0;
          }
        }
        continue;
      }
      for (int submask = i; submask; submask = (submask - 1) & i)
      {
        for (int my_root = 0; my_root < n; ++my_root)
        {
          if ((i & (1 << my_root)) && !(submask & (1 << my_root)))
          {
            for (int new_root = 0; new_root < n; ++new_root)
            {
              if (submask & (1 << new_root))
              {
                dp[i][my_root] = min(dp[i][my_root], a[my_root][new_root] + max(dp[i ^ submask][my_root], dp[submask][new_root]));
              }
            }
          }
        }
      }
    }
    fout << dp[(1 << n) - 1][0] << '\n';
  }
}