// horizon
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

typedef int Pos;

#define CAR1(x) (x&0xff)
#define CAR2(x) ((x>>8)&0xff)
#define CAR3(x) ((x>>16)&0xff)
#define NEXT(x) ((x>>24)&0xff)

Pos MakePos(int x, int y, int z, int t)
{
  if(x > y)
    swap(x,y);
  if(x > z)
    swap(x,z);
  if(y > z)
    swap(y,z);
  return (x|(y<<8)|(z<<16)|(t<<24));
}

int n;
multimap<int, Pos> state;
map<Pos, int> cache;
int cost[30][30];

void Add(Pos p, int t)
{
  map<Pos, int>::iterator i = cache.find(p);
  if(i == cache.end() || i->second > t) {
    state.insert(make_pair(t, p));
    cache[p] = t;
  }
}

int Run()
{
  state.clear();
  cache.clear();
  state.insert(make_pair(0, MakePos(0,0,0,1)));
  while(true) {
    Pos cur = state.begin()->second;
    int time = state.begin()->first;
    state.erase(state.begin());
    int c1 = CAR1(cur);
    int c2 = CAR2(cur);
    int c3 = CAR3(cur);
    int next = NEXT(cur);
    if(next == n)
      return time;
    Add(MakePos(next, c2, c3, next+1), time + cost[c1][next]);
    Add(MakePos(c1, next, c3, next+1), time + cost[c2][next]);
    Add(MakePos(c1, c2, next, next+1), time + cost[c3][next]);
  }
}

int main()
{
  ifstream cin("magazine.txt");
  int M;
  cin >> M;
  for(int cnt = 0; cnt < M; ++cnt) {
    cin >> n;
    for(int i = 0; i < n; ++i) {
      cost[i][i] = 0;
      for(int j = i+1; j < n; ++j) {
	cin >> cost[i][j];
	cost[j][i] = cost[i][j];
      }
    }
    for(int k = 0; k < n; ++k)
      for(int i = 0; i < n; ++i)
	for(int j = 0; j < n; ++j) {
	  if(cost[i][j] > cost[i][k] + cost[k][j])
	    cost[i][j] = cost[i][k] + cost[k][j];
	}
    cout << Run() << endl;
  }
}