//和双调欧几里德旅行商一样的做法。参见前面的双调欧几里德旅行商问题
#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;
}