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

struct muchie {
    int x, y, cost;
    muchie(int _x, int _y, int _cost) : x(_x), y(_y), cost(_cost) {}
    bool operator < (const muchie& b) const {
        if (cost == b.cost) {
            if (x == b.x)
                return y < b.y;
            return x < b.x;
        }
        return cost < b.cost;
    }
};
vector<muchie> muchii;
int n,t[15];


int testCase()
{
    muchii.clear();
    fin >> n;

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            int cost;
            fin >> cost;
            if (i == j) continue;
            muchii.push_back(muchie(i,j,cost));
        }
    }
    sort(muchii.begin(), muchii.end());

    //initializam reprezentantii
    for(int i=1;i<=n;i++)
        t[i]=i;
    //determinam A.P.M.
    int S=0;
    for(int i=0; i<muchii.size(); i++)
    {
        muchie& m = muchii[i];
        //cout<<"M "<<m.x<<' '<<m.y<<' '<<m.cost<<endl;
        if(t[m.x] != t[m.y])//extremitatile fac parte din arbori diferiti
        {
            S+=m.cost;
            //reunim subarborii
            int ai=t[m.x],aj=t[m.y];
            for(int j=1;j<=n;j++)
                if(t[j]==aj)
                    t[j]=ai;
        }
    }

    return S;
}

int main()
{
    int nc;
    fin >> nc;
    while (nc--)
        fout << testCase() << endl;
}