# include <algorithm>
# include <cstdio>
# include <cstring>
# include <vector>
using namespace std;

const char *FIN = "cast.in", *FOU = "cast.out";
const int MAX = 12;

int N, T;
vector < vector <int> > dp, time;

int solve (int state, int poz) {
    if (dp[poz][state] < 0x3f3f3f3f) return dp[poz][state];

    vector <int> vec;
    for (int i = 0; i < N; ++i)
        if (i != poz && (state & (1 << i)))
            vec.push_back (i);
    for (int bit = 0, size = vec.size (); bit < (1 << size); ++bit) {
        int newstate = 0;
        for (vector <int> :: iterator it = vec.begin (); it != vec.end (); ++it)
            if (bit & (1 << (it - vec.begin ())))
                newstate |= 1 << *it;
        for (vector <int> :: iterator it = vec.begin (); it != vec.end (); ++it)
            if (newstate & (1 << *it))
                dp[poz][state] = min (dp[poz][state], time[poz][*it] + max (solve (state ^ newstate, poz),
                                                                            solve (newstate, *it)));
    }
    return dp[poz][state];
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    for (scanf ("%d", &T); T; --T) {
        scanf ("%d", &N);
        time.resize (N + 1), dp.resize (N + 1);
        for (int i = 0; i < N; ++i) {
            time[i].resize (N + 1, 0), dp[i].resize ((1 << N) + 1, 0x3f3f3f3f);
            printf ("1 %d\n", dp[i][1 << i]);
            dp[i][1 << i] = 0;
            printf ("2 %d\n", dp[i][1 << i]);
            for (int j = 0, k; j < N; ++j)
                scanf ("%d", &k), time[i][j] = k;
        }
        printf ("%d\n", solve ((1 << N) - 1, 0));
    }
}