///gnc
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include<sstream>
#include<cassert>
#include<string>

using namespace std;

const int INF = 9999;

typedef map<string, int> car_history;
typedef multiset<int> cars;

string strhash(const cars & c){
  ostringstream os;
  cars::const_iterator it = c.begin();
  for(; it != c.end(); ++it){
    os << *it << " ";
  }
  return os.str();
}

int main(void)
{
  int n;
  ifstream is("magazine.txt");
  is >>n;
  for(int nc = 0; nc < n; nc ++){
    int nn;
    is >> nn;
    int d[nn][nn];
    for(int i = 0; i < nn; i++){
      d[i][i] = INF;
      for(int j = i + 1; j < nn; j++){
        int cost;
        is >> cost;
        d[i][j] = cost;
        d[j][i] = cost;
      }
    }
    for(int l = 0; l < nn; l++)
      for(int i = 0; i < nn; i++)
        for(int j = 0; j < nn; j++)
          d[i][j] = min ( d[i][j], d[i][l] + d[l][j]);
    cars c;
    c.insert(0);    c.insert(0);    c.insert(0);
    car_history costs;
    costs[strhash(c)] = 0;
    for(int l = 1; l < nn; l++){
//      cout << l << endl;
      car_history newcosts;
      for(int i = 0; i < l; i++){
//        cout << "i" << i << endl;
        for(int j = i; j < l; j++){
//          cout << "j" << j << endl;
          cars old_stat;
          old_stat.insert(i);
          old_stat.insert(j);
          old_stat.insert(l-1);
          car_history::iterator it =
            costs.find(strhash(old_stat));
          if(it == costs.end() ){
//            cout << i << " " << j << " " << l-1 << endl;
            continue;
          }
          cars::const_iterator cit;
//          cout << "build new" << endl;
          for(cit = old_stat.begin();
              cit != old_stat.end();
              ++cit){
//            cout << "before cost" << endl;
            int newcost = it -> second + (d[*cit][l]);
//            cout << "after cost" << endl;
            cars nc(old_stat);
            nc.erase(nc.find(*cit));
            nc.insert(l);
            if(newcosts.find(strhash(nc)) == newcosts.end())
              newcosts[strhash(nc)] = newcost;
            else
              newcosts[strhash(nc)] = min(newcosts[strhash(nc)], newcost);
          }
        }
      }
      costs = newcosts;
      for(car_history::iterator it = newcosts.begin();
          it != newcosts.end();
          it++){
//        cout << "cost of" << it ->first << " is " << it -> second << endl;
      }
    }
    int mini = INF;
    for(car_history::iterator it = costs.begin();
        it != costs.end();
        it++){
      mini = min(it -> second, mini); 
    }
    cout << mini << endl;
  }
}