////////combat

#include <fstream>
#include <iostream>
#include <deque>
using namespace std;

int main()
{
  ifstream cin("magazine.txt");

  int cases;cin>>cases;
  while(cases--){
    int city;cin>>city;

    int i,j,k,l;
    int dist[30][30]={0};
    for (i=0;i<city-1;i++)
      for (j=i+1;j<city;j++){
        cin>>dist[i][j];
        dist[j][i]=dist[i][j];
      }
    for (i=0;i<city;i++)
      dist[i][i]=0;

    static int tbl[30][30][30][30];
    for (i=0;i<30;i++)
      for (j=0;j<30;j++)
        for (k=0;k<30;k++)
          for (l=0;l<30;l++)
            tbl[i][j][k][l]=INT_MAX;
    deque<int> q;
    q.push_back(0);
    tbl[0][0][0][0]=0;
    while(!q.empty()){
      int tmp=q.front();
      q.pop_front();
      int n=tmp/(30*30*30);
      int x=(tmp/(30*30))%30;
      int y=(tmp/30)%30;
      int z=tmp%30;
//      cout<<n<<" "<<x<<" "<<y<<" "<<z<<": "<<tbl[n][x][y][z]<<endl;

      for (i=0;i<=city-1;i++){
        if (i==x) continue;
        int c=tbl[n][x][y][z]+dist[x][i];
        int nn=(i==(n+1))?(n+1):n;
        if (c<tbl[nn][i][y][z]){
          tbl[nn][i][y][z]=c;
          q.push_back(nn*30*30*30+i*30*30+y*30+z);
        }
      }
      for (i=0;i<=city-1;i++){
        if (i==y) continue;
        int c=tbl[n][x][y][z]+dist[y][i];
        int nn=(i==(n+1))?(n+1):n;
        if (c<tbl[nn][x][i][z]){
          tbl[nn][x][i][z]=c;
          q.push_back(nn*30*30*30+x*30*30+i*30+z);
        }
      }
      for (i=0;i<=city-1;i++){
        if (i==z) continue;
        int c=tbl[n][x][y][z]+dist[z][i];
        int nn=(i==(n+1))?(n+1):n;
        if (c<tbl[nn][x][y][i]){
          tbl[nn][x][y][i]=c;
          q.push_back(nn*30*30*30+x*30*30+y*30+i);
        }
      }
    }

    int ans=INT_MAX;
    for (i=0;i<city;i++){
      for (j=0;j<city;j++){
        for (k=0;k<city;k++){
          ans=min(ans,tbl[city-1][i][j][k]);
        }
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}