#include <bits/stdc++.h>

const int BITS = 12;
const int MAX_N = 1 << BITS;
const int INF = 1 << 25;

int n, t;

int cost[BITS][BITS];
int dp[MAX_N][BITS];

int main() {
  int subSet, newMask;
  freopen("cast.in", "r", stdin);
  freopen("cast.out", "w", stdout);
  std::cin >> t;
  while (t --) {
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        std::cin >> cost[i][j];
      }
    }
    for (int mask = 0; mask < (1 << n); ++mask) {
      for (int i = 0; i < n; ++i) {
        dp[mask][i] = INF;
      }
    }
    for (int mask = 1; mask < (1 << n); ++mask) {
      for (int i = 0; i < n; ++i) {
        if ((mask & (1 << i)) > 0) {
          if ((mask & (1 << i)) == mask) {
            dp[mask][i] = 0;
          } else {
            newMask = subSet = (mask ^ (1 << i));
            while (newMask > 0) {
              for (int j = 0; j < n; ++j) {
                if ((newMask & (1 << j)) > 0) {
                  dp[mask][i] = std::min(dp[mask][i], cost[i][j] +
                                std::max(dp[mask ^ newMask][i], dp[newMask][j]));
                }
              }
              newMask = ((newMask - 1) & subSet);
            }
          }
        }
      }
    }
    std::cout << dp[(1 << n) - 1][0] << "\n";
  }
  return 0;
}