/** GOKURI */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <cassert>
using namespace std;

#define FNAME "magazine.txt"
#define cin fin

struct taxis {
  int a,b,c;
};
bool operator<( const taxis& t1, const taxis& t2 )
{
  if( t1.a != t2.a ) return t1.a < t2.a;
  if( t1.b != t2.b ) return t1.b < t2.b;
  return t1.c < t2.c;
}

typedef taxis vert;
typedef int   len_t;
typedef pair<len_t,vert> edge;
typedef vector<edge> edges;
typedef map<vert,edges> graph;

len_t dijkstra( graph& G, vert src, int N )
{
  set<vert> visited;
  priority_queue<edge, vector<edge>, greater<edge> > Q;
  Q.push( edge(0,src) );
  while( !Q.empty() )
    {
      edge c = Q.top(); Q.pop();
      if( visited.count(c.second) )
        continue;
      if( c.second.a==N || c.second.b==N || c.second.c==N )
        return c.first;
      visited.insert( c.second );
      edges& ne = G[c.second];
      for(int i=0; i!=ne.size(); ++i)
        if( !visited.count(ne[i].second) )
          Q.push( edge(c.first+ne[i].first, ne[i].second) );
    }
  assert(false);
}

int main()
{
  ifstream fin(FNAME);
  if(!fin) return -1;

  int N; cin >> N;
  while(N--)
    {
      // input
      int nLoc; cin >> nLoc;
      vector< vector<int> > D( nLoc, vector<int>(nLoc,0) );
      for(int i=0; i<nLoc; ++i)
        for(int j=i+1; j<nLoc; ++j)
          {
            int x; cin>>x;
            D[i][j] = D[j][i] = x;
          }

      // WF
      for(int k=0; k<nLoc; ++k)
        for(int i=0; i<nLoc; ++i)
          for(int j=0; j<nLoc; ++j)
            D[i][j] = min( D[i][j], D[i][k]+D[k][j] );

      // make graph
      graph G;
      for(int i=0; i<nLoc-1; ++i)
        for(int j=0; j<nLoc-1; ++j)
          for(int k=0; k<nLoc-1; ++k)
            {
              vert v = {i,j,k};
              int M = max(i,max(j,k));
              {
                vert u = {i,j,M+1};
                G[v].push_back( edge(D[k][M+1],u) );
              }
              {
                vert u = {i,M+1,k};
                G[v].push_back( edge(D[j][M+1],u) );
              }
              {
                vert u = {M+1,j,k};
                G[v].push_back( edge(D[i][M+1],u) );
              }
            }

      // output
      vert src = {0,0,0};
      cout << dijkstra(G,src,nLoc-1) << endl;
    }
  return 0;
}