//和双调欧几里德旅行商一样的做法。参见前面的双调欧几里德旅行商问题
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,L,R) for(int i=L;i<=R;i++)
#define INF 10000000
using namespace std;
int cas;
int dp[31][31][31];
int map[31][31];
int n;
int main()
{
scanf("%d",&cas);
while(cas--)
{
memset(map,0,sizeof(map));
scanf("%d",&n);
REP(i,n)
REP(j,n)
{
if(j>i)
scanf("%d",&map[i][j]);
fill_n(dp[i][j],n,INF);
}
dp[0][0][0]=0;
REP(i,n)
{
REP(j,i+1)
{
REP(k,j+1)
{
dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]+map[i][i+1]);//to i
dp[i+1][i][k]=min(dp[i+1][i][k],dp[i][j][k]+map[j][i+1]);//to j
dp[i+1][i][j]=min(dp[i+1][i][j],dp[i][j][k]+map[k][i+1]);//to k
}
}
}
int ma=INF;
REP(i,n)
REP(j,i+1)
ma=min(ma,dp[n-1][i][j]);
printf("%d\n",ma);
}
return 0;
}